Approximating Binary Longest Common Subsequence in Almost-Linear Time

The Longest Common Subsequence (LCS) is a fundamental string similarity measure, and computing the LCS of two strings is a classic algorithms question. A textbook dynamic programming algorithm gives an exact algorithm in quadratic time, and this is essentially best possible under plausible fine-grained complexity assumptions, so a natural problem is to find faster approximation algorithms. When the inputs are two binary strings, there is a simple 1/2-approximation in linear time: compute the longest common all-0s or all-1s subsequence. It has been open whether a better approximation is possible even in truly subquadratic time. Rubinstein and Song showed that the answer is yes under the assumption that the two input strings have equal lengths. We settle the question, generalizing their result to unequal length strings, proving that, for any ε>0, there exists δ>0 and a (1/2+δ)-approximation algorithm for binary LCS that runs in n 1+ε time. As a consequence of our result and a result of Akmal and Vassilevska-Williams, for any ε>0, there exists a (1/ q +δ)-approximation for LCS over q -ary strings in n 1+ε time.

Authors

• Xiaoyu He
• Ray Li

Keywords

• almost-linear time
• approximation algorithms
• deletion codes
• longest common subsequence