Sketching, Streaming, and Fine-Grained Complexity of (Weighted) LCS

We study sketching and streaming algorithms for the Longest Common Subsequence problem (LCS) on strings of small alphabet size $\mathrm{\mid }\mathrm{\Sigma }\mathrm{\mid }$. For the problem of deciding whether the LCS of strings $x,y$ has length at least $L$, we obtain a sketch size and streaming space usage of $$\mathcal{O}$(L^{|\Sigma| - 1} \log L)$. We also prove matching unconditional lower bounds. As an application, we study a variant of LCS where each alphabet symbol is equipped with a weight that is given as input, and the task is to compute a common subsequence of maximum total weight. Using our sketching algorithm, we obtain an $$\mathcal{O}$($\text{min}${nm, n + m^{{\lvert \Sigma \rvert}}})$-timealgorithmforthisproblem,onstrings$x,y$oflength$n,m$, with $n\ge m$. We prove optimality of this running time up to lower order factors, assuming the Strong Exponential Time Hypothesis.