Abstract
Longest common subsequence (LCS) is one of the most fundamental problems in combinatorial optimization. Apart from theoretical importance, LCS has enormous applications in bioinformatics, revision control systems, and data comparison programs. Although a simple dynamic program computes LCS in quadratic time, it has been recently proven that the problem admits a conditional lower bound and may not be solved in truly subquadratic time. In addition to this, LCS is notoriously hard with respect to approximation algorithms. Apart from a trivial sampling technique that obtains a $n^{x}$ approximation solution in time $O(n^{2-2x})$ nothing else is known for LCS. This is in sharp contrast to its dual problem edit distance for which several linear time solutions are obtained in the past two decades.
Introduction
The Longest Common Subsequence (LCS) problem is a cornerstone of computer science, asking for the longest string that can be derived from two input strings, $s$ and $\bar{s}$, by deleting characters. While it powers essential tools like the UNIX diff command and DNA sequence alignment, its computational complexity has long been a bottleneck.
Modern "Fine-Grained Complexity" research suggests that a truly subquadratic algorithm (e.g., $O(n^{1.99})$) might be impossible under standard complexity assumptions. Consequently, research has shifted toward approximation. For decades, the best linear-time approximation factor remained stuck at $O(\sqrt{n})$, a barrier achieved by simple sampling. This paper breaks that barrier, providing the first linear-time algorithm with an approximation factor better than $\sqrt{n}$.
Algorithmic Framework
The authors achieve this breakthrough by employing a suite of four distinct algorithms. The core idea is that for any given pair of strings, at least one of these strategies is guaranteed to yield a high-quality approximation.
- Small Solution Size: A modified sampling technique designed for cases where the actual LCS is relatively short.
- Frequency-Based Filtering: This method categorizes symbols based on their frequency. It utilizes a randomized version of the Apostolico-Guerra algorithm to handle instances dominated by low-frequency characters.
- Block-to-Block Comparison: The input strings are partitioned into $\sqrt{n}$ blocks. This algorithm targets "crebris" (frequent) characters—symbols appearing many times within specific block pairs—using a high-level dynamic programming approach.
- Random Shifting for Infrequent Characters: This novel component targets "rarus" (infrequent) characters. By transforming blocks into "semi-permutations" (where each symbol appears at most once), the algorithm uses random shifts to align blocks and find commonalities.
To validate the effectiveness of the random shifting approach, the authors utilize advanced combinatorial tools, including Dilworth’s Theorem for partially ordered sets and Turán’s Theorem from graph theory. These theorems prove that even in seemingly difficult instances, random blocks are likely to share a significant common subsequence.
Key Insights: Crebris vs. Rarus
A pivotal contribution of this work is the structural distinction between characters in the optimal solution. By categorizing characters as either crebris (frequent) or rarus (infrequent), the authors can apply specialized algorithmic tools to different string structures.
Furthermore, the final approximation factor of $O(n^{0.497956})$ was derived through Linear Programming (LP) optimization. The authors modeled various parameters—such as solution size and symbol distribution—and used the LP to identify the "worst-case" scenario, ensuring their combined algorithms beat the $\sqrt{n}$ limit regardless of input.
Results and Significance
The primary result is a linear-time algorithm (running in $O(n)$ or $O(n \log n)$) that achieves an approximation factor of $O(n^{0.497956})$. While the numerical improvement over $n^{0.5}$ is small, its theoretical significance is immense, proving that the $\sqrt{n}$ barrier is not a fundamental limit for linear-time LCS.
Limitations and Future Outlook
While a major theoretical milestone, the practical impact of the $0.002$ exponent improvement is minimal for standard string lengths. Additionally, a significant gap remains between the approximation capabilities for LCS and its dual problem, Edit Distance (which enjoys polylogarithmic approximations). Future research will likely focus on closing this gap or determining if LCS is inherently more difficult to approximate in linear time.
Summary updated