Bounded Edit Distance: Optimal Static and Dynamic Algorithms for Small Integer Weights

Weighted edit distance is one of the classic examples of dynamic programming taught in algorithms courses. Nearly 40 years ago, Landau and Vishkin gave a celebrated O(n+k^2)-time algorithm for the unit-cost version, where n is the string length and k is the edit distance. Fine-grained complexity results have since shown this running time to be
conditionally optimal. However, while theory has largely focused on unit weights, real-world applications—especially in bioinformatics—often use rational edit costs with small (constantly bounded) numerators and
denominators. For such weights—even simple ones like {1,2,3}—the Landau-Vishkin algorithm breaks down.
In this work, we show how to recover the time complexity of Landau and Vishkin’s algorithm (up to polylogarithmic factors) for any fixed rational weight function.