Document Open Access Logo

A Sub-Quadratic Algorithm for the Longest Common Increasing Subsequence Problem

Author Lech Duraj

PDF

File

Thumbnail PDF
PDF
LIPIcs.STACS.2020.41.pdf
  • Filesize: 0.6 MB
  • 18 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • longest common increasing subsequence
  • log-shaving
  • matching pairs

Metrics

Abstract

The Longest Common Increasing Subsequence problem (LCIS) is a natural variant of the celebrated Longest Common Subsequence (LCS) problem. For LCIS, as well as for LCS, there is an ?(n²)-time algorithm and a SETH-based conditional lower bound of ?(n^{2-ε}). For LCS, there is also the Masek-Paterson ?(n²/log n)-time algorithm, which does not seem to adapt to LCIS in any obvious way. Hence, a natural question arises: does any (slightly) sub-quadratic algorithm exist for the Longest Common Increasing Subsequence problem? We answer this question positively, presenting a ?(n²/log^a n)-time algorithm for a = 1/6-o(1). The algorithm is not based on memorizing small chunks of data (often used for logarithmic speedups, including the "Four Russians Trick" in LCS), but rather utilizes a new technique, bounding the number of significant symbol matches between the two sequences.

Cite As Get BibTex

Lech Duraj. A Sub-Quadratic Algorithm for the Longest Common Increasing Subsequence Problem. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 41:1-41:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.STACS.2020.41

Author Details

Lech Duraj
  • Theoretical Computer Science, Faculty of Mathematics and Computer Science, Jagiellonian University, Kraków, Poland

Funding

  • Duraj, Lech: This work was partially supported by Polish National Science Center grant 2016/21/B/ST6/ 02165.

Acknowledgements

I would like to thank Grzegorz Guśpiel, Grzegorz Herman and Adam Polak for helpful discussions and proofreading the paper, as well as the reviewers for many insightful comments and suggestions.

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 and Karl Bringmann. Tighter connections between formula-sat and shaving logs. In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, pages 8:1-8:18, 2018. URL: https://doi.org/10.4230/LIPIcs.ICALP.2018.8.
  3. 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 Proceedings of the Forty-eighth Annual ACM Symposium on Theory of Computing, STOC '16, pages 375-388, New York, NY, USA, 2016. ACM. URL: https://doi.org/10.1145/2897518.2897653.
  4. Karl Abrahamson. Generalized string matching. SIAM J. Comput., 16(6):1039–1051, December 1987. URL: https://doi.org/10.1137/0216067.
  5. Moshe Lewenstein Amihood Amir and Ely Porat. Faster algorithms for string matching with k mismatches. In J. of Algorithms, pages 794-803, 2000. Google Scholar
  6. 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
  7. Ilya Baran, Erik D. Demaine, and Mihai Pǎtraşcu. Subquadratic algorithms for 3sum. In Proceedings of the 9th International Conference on Algorithms and Data Structures, WADS'05, pages 409-421, Berlin, Heidelberg, 2005. Springer-Verlag. URL: https://doi.org/10.1007/11534273_36.
  8. 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), pages 1216-1235, 2018. Google Scholar
  9. Timothy M. Chan. The art of shaving logs. In Frank Dehne, Roberto Solis-Oba, and Jörg-Rüdiger Sack, editors, Algorithms and Data Structures, pages 231-231, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg. Google Scholar
  10. Timothy M. Chan. More logarithmic-factor speedups for 3sum, (median,+)-convolution, and some geometric 3sum-hard problems. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '18, pages 881-897, Philadelphia, PA, USA, 2018. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=3174304.3175327.
  11. 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
  12. Lech Duraj. A linear algorithm for 3-letter longest common weakly increasing subsequence. Information Processing Letters, 113(3):94-99, 2013. Google Scholar
  13. Lech Duraj, Marvin Künnemann, and Adam Polak. Tight conditional lower bounds for longest common increasing subsequence. Algorithmica, 81(10):3968-3992, October 2019. URL: https://doi.org/10.1007/s00453-018-0485-7.
  14. Szymon Grabowski. New tabulation and sparse dynamic programming based techniques for sequence similarity problems. Discrete Applied Mathematics, 212:96-103, 2016. URL: https://doi.org/10.1016/j.dam.2015.10.040.
  15. Yijie Han and Tadao Takaoka. An o(n³ log log n/log² n) time algorithm for all pairs shortest paths. In Fedor V. Fomin and Petteri Kaski, editors, Algorithm Theory - SWAT 2012, pages 131-141, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg. Google Scholar
  16. Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-SAT. Journal of Computer and System Sciences, 62(2):367-375, 2001. Google Scholar
  17. 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
  18. 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
  19. Martin Kutz, Gerth Stølting Brodal, Kanela Kaligosi, and Irit Katriel. Faster algorithms for computing longest common increasing subsequences. J. Discrete Algorithms, 9(4):314-325, 2011. URL: https://doi.org/10.1016/j.jda.2011.03.013.
  20. Kasper Green Larsen and Ryan Williams. Faster online matrix-vector multiplication. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '17, pages 2182-2189, Philadelphia, PA, USA, 2017. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=3039686.3039828.
  21. 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
  22. Kurt Mehlhorn and Stefan Näher. Bounded ordered dictionaries in o(log log N) time and o(n) space. Inf. Process. Lett., 35(4):183-189, 1990. URL: https://doi.org/10.1016/0020-0190(90)90022-P.
  23. Adam Polak. Why is it hard to beat O(n²) for longest common weakly increasing subsequence? Information Processing Letters, 132:1-5, 2018. Google Scholar
  24. 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
  25. Yoshifumi Sakai. A linear space algorithm for computing a longest common increasing subsequence. Inf. Process. Lett., 99(5):203-207, 2006. URL: https://doi.org/10.1016/j.ipl.2006.05.005.
  26. P. van Emde Boas. Preserving order in a forest in less than logarithmic time. In Proceedings of the 16th Annual Symposium on Foundations of Computer Science, SFCS '75, pages 75-84, Washington, DC, USA, 1975. IEEE Computer Society. URL: https://doi.org/10.1109/SFCS.1975.26.
  27. Robert A. Wagner and Michael J. Fischer. The string-to-string correction problem. Journal of the ACM, 21(1):168-173, 1974. Google Scholar
  28. Ryan Williams. A new algorithm for optimal 2-constraint satisfaction and its implications. Theoretical Computer Science, 348(2):357-365, 2005. Google Scholar
  29. Ryan Williams. Matrix-vector multiplication in sub-quadratic time: (some preprocessing required). In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '07, pages 995-1001, Philadelphia, PA, USA, 2007. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=1283383.1283490.
  30. Ryan Williams. Faster all-pairs shortest paths via circuit complexity. In Proceedings of the Forty-sixth Annual ACM Symposium on Theory of Computing, STOC '14, pages 664-673, New York, NY, USA, 2014. ACM. URL: https://doi.org/10.1145/2591796.2591811.
  31. 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
  32. Daxin Zhu and Xiaodong Wang. A space efficient algorithm for lcis problem. In Guojun Wang, Mohammed Atiquzzaman, Zheng Yan, and Kim-Kwang Raymond Choo, editors, Security, Privacy, and Anonymity in Computation, Communication, and Storage, pages 70-77, Cham, 2017. Springer International Publishing. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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