License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2017.15
URN: urn:nbn:de:0030-drops-85706
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8570/
Go to the corresponding LIPIcs Volume Portal

Duraj, Lech ; Künnemann, Marvin ; Polak, Adam

Tight Conditional Lower Bounds for Longest Common Increasing Subsequence

pdf-format:
LIPIcs-IPEC-2017-15.pdf (0.6 MB)

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 LCS. We further strengthen this lower bound to rule out O((nL)^{1-epsilon}) time algorithms for LCIS, where L denotes the solution size, and to rule out O(n^{k-epsilon}) time algorithms for k-LCIS. We obtain the same conditional lower bounds for the related Longest Common Weakly Increasing Subsequence problem.

BibTeX - Entry

@InProceedings{duraj_et_al:LIPIcs:2018:8570,
  author =	{Lech Duraj and Marvin K{\"u}nnemann and Adam Polak},
  title =	{{Tight Conditional Lower Bounds for Longest Common Increasing Subsequence}},
  booktitle =	{12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
  pages =	{15:1--15:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-051-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{89},
  editor =	{Daniel Lokshtanov and Naomi Nishimura},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8570},
  URN =		{urn:nbn:de:0030-drops-85706},
  doi =		{10.4230/LIPIcs.IPEC.2017.15},
  annote =	{Keywords: fine-grained complexity, combinatorial pattern matching, sequence alignments, parameterized complexity, SETH}
}

Keywords: fine-grained complexity, combinatorial pattern matching, sequence alignments, parameterized complexity, SETH
Collection: 12th International Symposium on Parameterized and Exact Computation (IPEC 2017)
Issue Date: 2018
Date of publication: 02.03.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI