Optimal Algorithms for Bounded Weighted Edit Distance

The edit distance (also known as Levenshtein distance) of two strings is the minimum number of insertions, deletions, and substitutions of characters needed to transform one string into the other. The textbook dynamic-programming algorithm computes the edit distance of two length- n strings in $\mathcal{O}\left(n^{2}\right)$ time, which is optimal up to subpolynomial factors assuming the Strong Exponential Time Hypothesis (SETH). An established way of circumventing this hardness is to consider the bounded setting, where the running time is parameterized by the edit distance k. A celebrated algorithm by Landau and Vishkin (JCSS’88) achieves a running time of $\mathcal{O}\left(n+k^{2}\right)$, which is optimal as a function of n and k (again, up to subpolynmial factors and assuming SETH).While the theory community thoroughly studied the Levenshtein distance, most practical applications rely on a more general weighted edit distance, where each edit has a weight depending on its type and the involved characters from the alphabet $\Sigma$. This is formalized through a weight function $w: \Sigma \cup\{\varepsilon\} \times \Sigma \cup\{\varepsilon\} \rightarrow \mathbb{R}$ normalized so that $w(a \mapsto a)=0$ for $a \in \Sigma \cup\{\varepsilon\}$ and $w(a \mapsto b) \geq 1$ for $a, b \in \Sigma \cup\{\varepsilon\}$ with $a \neq b$; the goal is to find an alignment of the two strings minimizing the total weight of edits. The classic $\mathcal{O}\left(n^{2}\right)$-time algorithm supports this setting seamlessly, but for many decades just a straightforward $\mathcal{O}(n k)$-time solution was known for the bounded version of the weighted edit distance problem. Only very recently, Das, Gilbert, Hajiaghayi, Kociumaka, and Saha (STOC’23) gave the first non-trivial algorithm, achieving a time complexity of $\mathcal{O}\left(n+k^{5}\right)$. While this running time is linear for $k \leq n^{1 / 5}$, it is still very far from $\mathcal{O}\left(n+k^{2}\right)$-the bound achievable in the unweighted setting. This is unsatisfactory, especially given the lack of any compelling evidence that the weighted version is inherently harder.In this paper, we essentially close this gap by showing both an improved $\widetilde{\mathcal{O}}\left(n+\sqrt{n k^{3}}\right)$-time algorithm and, more surprisingly, a matching lower bound: Conditioned on the All-Pairs Shortest Paths (APSP) hypothesis, the running time of our solution is optimal for $\sqrt{n} \leq k \leq n$ (up to subpolynomial factors). In particular, this is the first separation between the complexity of the weighted and unweighted edit distance problems.Just like the Landau-Vishkin algorithm, our algorithm can be adapted to a wide variety of settings, such as when the input is given in a compressed representation. This is because, independently of the string length n, our procedure takes $\widetilde{\mathcal{O}}\left(k^{3}\right)$ time assuming that the equality of any two substrings can be tested in $\widetilde{\mathcal{O}}(1)$ time.Consistently with the previous work, our algorithm relies on the observation that strings with a rich structure of low-weight alignments must contain highly repetitive substrings. Nevertheless, achieving the optimal running time requires multiple new insights. We capture the right notion of repetitiveness using a tailor-made compressibility measure that we call self-edit distance. Our divide-and-conquer algorithm reduces the computation of weighted edit distance to several subproblems involving substrings of small self-edit distance and, at the same time, distributes the budget for edit weights among these subproblems. We then exploit the repetitive structure of the underlying substrings using state-of-the-art results for multiple-source shortest paths in planar graphs (Klein, SODA’05).As a stepping stone for our conditional lower bound, we study a dynamic problem of maintaining two strings subject to updates (substitutions of characters) and weighted edit distance queries. We significantly extend the construction of Abboud and Dahlgaard (FOCS’16), originally for dynamic shortest paths in planar graphs, to show that a sequence of n updates and $q \leq n$ queries cannot be handled much faster than in $\mathcal{O}\left(n^{2} \sqrt{q}\right)$ time. We then compose the snapshots of the dynamic strings to derive hardness of the static problem in the bounded setting.