Document Open Access Logo

Tight Conditional Lower Bounds for Longest Common Increasing Subsequence

Authors Lech Duraj, Marvin Künnemann, Adam Polak

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2017.15.pdf
  • Filesize: 0.62 MB
  • 13 pages

Document Identifiers

Author Details

Lech Duraj
Marvin Künnemann
Adam Polak

Cite As Get BibTex

Lech Duraj, Marvin Künnemann, and Adam Polak. Tight Conditional Lower Bounds for Longest Common Increasing Subsequence. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 15:1-15:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.IPEC.2017.15

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.

Subject Classification

Keywords
  • fine-grained complexity
  • combinatorial pattern matching
  • sequence alignments
  • parameterized complexity
  • SETH

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams. Quadratic-time hardness of LCS and other sequence similarity measures. In Proc. 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS'15), pages 59-78, 2015. Google Scholar
  2. Amir Abboud, Thomas Dueholm Hansen, Virginia Vassilevska Williams, and Ryan Williams. Simulating branching programs with edit distance and friends or: A polylog shaved is a lower bound made. In Proc. 48th Annual ACM Symposium on Symposium on Theory of Computing (STOC'16), pages 375-388, 2016. Google Scholar
  3. Amir Abboud, Virginia Vassilevska Williams, and Oren Weimann. Consequences of faster alignment of sequences. In Proc. of 41st International Colloquium on Automata, Languages, and Programming (ICALP'14), pages 39-51, 2014. Google Scholar
  4. Alfred V. Aho, Daniel S. Hirschberg, and Jeffrey D. Ullman. Bounds on the complexity of the longest common subsequence problem. Journal of the ACM, 23(1):1-12, 1976. Google Scholar
  5. Stephen F. Altschul, Warren Gish, Webb Miller, Eugene W. Myers, and David J. Lipman. Basic local alignment search tool. Journal of Molecular Biology, 215(3):403-410, 1990. Google Scholar
  6. Hsing-Yen Ann, Chang-Biau Yang, and Chiou-Ting Tseng. Efficient polynomial-time algorithms for the constrained LCS problem with strings exclusion. Journal of Combinatorial Optimization, 28(4):800-813, 2014. Google Scholar
  7. Alberto Apostolico and Concettina Guerra. The longest common subsequence problem revisited. Algorithmica, 2(1):316-336, 1987. Google Scholar
  8. Abdullah N. Arslan and Ömer Egecioglu. Algorithms for the constrained longest common subsequence problems. International Journal of Foundations of Computer Science, 16(6):1099-1109, 2005. Google Scholar
  9. Arturs Backurs and Piotr Indyk. Edit distance cannot be computed in strongly subquadratic time (unless SETH is false). In Proc. 47th Annual ACM Symposium on Theory of Computing (STOC'15), pages 51-58, 2015. Google Scholar
  10. Arturs Backurs and Piotr Indyk. Which regular expression patterns are hard to match? In Proc. 57th Annual Symposium on Foundations of Computer Science, (FOCS'16), pages 457-466, 2016. Google Scholar
  11. Arturs Backurs and Christos Tzamos. Improving viterbi is hard: Better runtimes imply faster clique algorithms. In Proc. 34th International Conference on Machine Learning (ICML'17), 2017. To appear. Google Scholar
  12. Gary Benson, Avivit Levy, S. Maimoni, D. Noifeld, and B. Riva Shalom. Lcsk: A refined similarity measure. Theoretical Computer Science, 638:11-26, 2016. Google Scholar
  13. Lasse Bergroth, Harri Hakonen, and Timo Raita. A survey of longest common subsequence algorithms. In Proc. 7th International Symposium on String Processing and Information Retrieval (SPIRE'00), pages 39-48, 2000. Google Scholar
  14. Karl Bringmann. Why walking the dog takes time: Frechet distance has no strongly subquadratic algorithms unless SETH fails. In Proc. 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS'14), pages 661-670, 2014. Google Scholar
  15. Karl Bringmann and Marvin Künnemann. Quadratic conditional lower bounds for string problems and dynamic time warping. In Proc. 56th Annual IEEE Symposium on Foundations of Compu ter Science (FOCS'15), pages 79-97, 2015. Google Scholar
  16. Karl Bringmann and Marvin Künnemann. Multivariate fine-grained complexity of longest common subsequence. In Proc. 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'18), 2018. To appear. Google Scholar
  17. Wun-Tat Chan, Yong Zhang, Stanley P. Y. Fung, Deshi Ye, and Hong Zhu. Efficient algorithms for finding a longest common increasing subsequence. Journal of Combinatorial Optimization, 13(3):277-288, 2007. Google Scholar
  18. Yi-Ching Chen and Kun-Mao Chao. On the generalized constrained longest common subsequence problems. Journal of Combinatorial Optimization, 21(3):383-392, 2011. Google Scholar
  19. Francis Y. L. Chin, Alfredo De Santis, Anna Lisa Ferrara, N. L. Ho, and S. K. Kim. A simple algorithm for the constrained sequence problems. Inf. Process. Lett., 90(4):175-179, 2004. URL: http://dx.doi.org/10.1016/j.ipl.2004.02.008.
  20. Vaclav Chvatal, David A. Klarner, and Donald E. Knuth. Selected combinatorial research problems. Technical Report CS-TR-72-292, Stanford University, Department of Computer Science, 6 1972. Google Scholar
  21. Maxime Crochemore and Ely Porat. Fast computation of a longest increasing subsequence and application. Information &Computation, 208(9):1054-1059, 2010. Google Scholar
  22. Marek Cygan, Marcin Mucha, Karol Wegrzycki, and Michal Wlodarczyk. On problems equivalent to (min,+)-convolution. In Proc. 44th International Colloquium on Automata, Languages, and Programming (ICALP'17), pages 22:1-22:15, 2017. Google Scholar
  23. Lech Duraj. A linear algorithm for 3-letter longest common weakly increasing subsequence. Information Processing Letters, 113(3):94-99, 2013. Google Scholar
  24. Michael L. Fredman. On computing the length of longest increasing subsequences. Discrete Mathematics, 11(1):29-35, 1975. Google Scholar
  25. Zvi Gotthilf, Danny Hermelin, Gad M. Landau, and Moshe Lewenstein. Restricted LCS. In Proc. 17th International Symposium on String Processing and Information Retrieval (SPIRE'10), pages 250-257, 2010. Google Scholar
  26. Daniel S. Hirschberg. Algorithms for the longest common subsequence problem. Journal of the ACM, 24(4):664-675, 1977. Google Scholar
  27. J. W. Hunt and M. D. McIlroy. An algorithm for differential file comparison. Computing Science Technical Report 41, Bell Laboratories, 1975. Google Scholar
  28. James W. Hunt and Thomas G. Szymanski. A fast algorithm for computing longest subsequences. Communications of the ACM, 20(5):350-353, 1977. Google Scholar
  29. Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-SAT. Journal of Computer and System Sciences, 62(2):367-375, 2001. Google Scholar
  30. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? Journal of Computer and System Sciences, 63(4):512-530, 2001. Google Scholar
  31. Guy Jacobson and Kiem-Phong Vo. Heaviest increasing/common subsequence problems. In Combinatorial Pattern Matching, Third Annual Symposium, CPM 92, Tucson, Arizona, USA, April 29 - May 1, 1992, Proceedings, pages 52-66, 1992. Google Scholar
  32. Tao Jiang, Guohui Lin, Bin Ma, and Kaizhong Zhang. The longest common subsequence problem for arc-annotated sequences. Journal of Discrete Algorithms, 2(2):257-270, 2004. Google Scholar
  33. Marvin Künnemann, Ramamohan Paturi, and Stefan Schneider. On the Fine-grained Complexity of One-Dimensional Dynamic Programming. In Proc. 44th International Colloquium on Automata, Languages, and Programming (ICALP'17), pages 21:1-21:15, 2017. Google Scholar
  34. Martin Kutz, Gerth Stølting Brodal, Kanela Kaligosi, and Irit Katriel. Faster algorithms for computing longest common increasing subsequences. Journal of Discrete Algorithms, 9(4):314-325, 2011. Google Scholar
  35. William J. Masek and Mike Paterson. A faster algorithm computing string edit distances. Journal of Computer and System Sciences, 20(1):18-31, 1980. Google Scholar
  36. Howard L. Morgan. Spelling correction in systems programs. Communications of the ACM, 13(2):90-94, 1970. Google Scholar
  37. Eugene W. Myers. An O(ND) difference algorithm and its variations. Algorithmica, 1(2):251-266, 1986. Google Scholar
  38. Saul B. Needleman and Christian D. Wunsch. A general method applicable to the search for similarities in the amino acid sequence of two proteins. Journal of Molecular Biology, 48(3):443-453, 1970. Google Scholar
  39. Adam Polak. Why is it hard to beat O(n²) for longest common weakly increasing subsequence? CoRR, abs/1703.01143, 2017. Google Scholar
  40. Liam Roditty and Virginia Vassilevska Williams. Fast approximation algorithms for the diameter and radius of sparse graphs. In Proc. 45th Annual ACM Symposium on Symposium on Theory of Computing (STOC'13), pages 515-524, 2013. Google Scholar
  41. Yin-Te Tsai. The constrained longest common subsequence problem. Information Processing Letters, 88(4):173-176, 2003. Google Scholar
  42. Robert A. Wagner and Michael J. Fischer. The string-to-string correction problem. Journal of the ACM, 21(1):168-173, 1974. Google Scholar
  43. Ryan Williams. A new algorithm for optimal 2-constraint satisfaction and its implications. Theoretical Computer Science, 348(2):357-365, 2005. Google Scholar
  44. Virginia Vassilevska Williams. Hardness of easy problems: Basing hardness on popular conjectures such as the strong exponential time hypothesis (invited talk). In Proc. 10th International Symposium on Parameterized and Exact Computation (IPEC'15), pages 17-29, 2015. Google Scholar
  45. I-Hsuan Yang, Chien-Pin Huang, and Kun-Mao Chao. A fast algorithm for computing a longest common increasing subsequence. Information Processing Letters, 93(5):249-253, 2005. Google Scholar
  46. Daxin Zhu, Lei Wang, Tinran Wang, and Xiaodong Wang. A simple linear space algorithm for computing a longest common increasing subsequence. CoRR, abs/1608.07002, 2016. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact