We consider the canonical generalization of the well-studied Longest Increasing Subsequence problem to multiple sequences, called k-LCIS: Given k integer sequences X-1, ... , X-k of length at most n, the task is to determine the length of the longest common subsequence of X-1, ... , X-k that is also strictly increasing. Especially for the case of k = 2 (called LCIS for short), several algorithms have been proposed that require quadratic time in the worst case. Assuming the Strong Exponential Time Hypothesis (SETH), we prove a tight lower bound, specifically, that no algorithm solves LCIS in (strongly) subquadratic time. Interestingly, the proof makes no use of normalization tricks common to hardness proofs for similar problems such as Longest Common Subsequence. We further strengthen this lower bound (1) to rule out O((nL)(1-epsilon)) time algorithms for LCIS, where L denotes the solution size, (2) to rule out O(n(k-epsilon)) time algorithms for k-LCIS, and (3) to follow already from weaker variants of SETH. We obtain the same conditional lower bounds for the related Longest Common Weakly Increasing Subsequence problem.

Tight conditional lower bounds for longest common increasing subsequence

Polak, Adam
2019

Abstract

We consider the canonical generalization of the well-studied Longest Increasing Subsequence problem to multiple sequences, called k-LCIS: Given k integer sequences X-1, ... , X-k of length at most n, the task is to determine the length of the longest common subsequence of X-1, ... , X-k that is also strictly increasing. Especially for the case of k = 2 (called LCIS for short), several algorithms have been proposed that require quadratic time in the worst case. Assuming the Strong Exponential Time Hypothesis (SETH), we prove a tight lower bound, specifically, that no algorithm solves LCIS in (strongly) subquadratic time. Interestingly, the proof makes no use of normalization tricks common to hardness proofs for similar problems such as Longest Common Subsequence. We further strengthen this lower bound (1) to rule out O((nL)(1-epsilon)) time algorithms for LCIS, where L denotes the solution size, (2) to rule out O(n(k-epsilon)) time algorithms for k-LCIS, and (3) to follow already from weaker variants of SETH. We obtain the same conditional lower bounds for the related Longest Common Weakly Increasing Subsequence problem.
2019
2018
Duraj, Lech; Künnemann, Marvin; Polak, Adam
File in questo prodotto:
File Dimensione Formato  
s00453-018-0485-7.pdf

accesso aperto

Descrizione: article
Tipologia: Pdf editoriale (Publisher's layout)
Licenza: Creative commons
Dimensione 662.65 kB
Formato Adobe PDF
662.65 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11565/4060536
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 9
  • ???jsp.display-item.citation.isi??? 1
social impact