2026-08-17T23:53:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11902 2024-03-06T10:48:58Z ddc:004 open_access

A Sub-Quadratic Algorithm for the Longest Common Increasing Subsequence Problem Duraj, Lech longest common increasing subsequence log-shaving matching pairs 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Lech Duraj 2020 Is Part Of LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2020.41 urn:nbn:de:0030-drops-119020 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.41 eng https://creativecommons.org/licenses/by/3.0/legalcode