A sub-quadratic algorithm for the longest common increasing subsequence problem

2019/02/19 by Duraj, Lech · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1902.06864

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 O(n²)-time algorithm and a SETH-based conditional lower bound of O(n^2-ε). For LCS, there is also the Masek-Paterson O(n² / logn)-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 O(n² / log^an)-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.

Cited by

• The Longest Common Bitonic Subsequence: A Match-Sensitive Dynamic Programming Approach

Related

• A Faster Subquadratic Algorithm for the Longest Common Increasing\n Subsequence Problem
• A Linear-Time n^0.4-Approximation for Longest Common Subsequence
• Approximating the Longest Common Subsequence problem within a sub-polynomial factor in linear time
• A Practical O(Rloglog n+n) time Algorithm for Computing the Longest Common Subsequence
• A simple linear space algorithm for computing a longest common increasing subsequence