Search Results

String Edit Distance is a more-than-classical problem whose behavior in the dynamic setting, where the strings are updated over time, is well studied. A single-character substitution, insertion, or deletion can be processed in time 𝒪̃(n w) when operation costs are positive integers bounded by w [Charalampopoulos, Kociumaka, Mozes, CPM 2020][Gorbachev, Kociumaka, STOC 2025]. If the weights are further uniform (insertions and deletions have equal cost), also an 𝒪̃(n √n)-update time algorithm exists [Charalampopoulos, Kociumaka, Mozes, CPM 2020]. This is a substantial improvement over the static 𝒪(n²) algorithm when w ≪ n or when we are dealing with uniform weights. In contrast, for inherently related problems such as Tree Edit Distance, Dyck Edit Distance, and RNA Folding, it has remained unknown whether it is possible to devise dynamic algorithms with an advantage over the static algorithm. In this paper, we resolve this question by showing that (weighted) Tree Edit Distance, Dyck Edit Distance, and RNA Folding admit no dynamic speedup: under well-known fine-grained assumptions, we show that the best possible algorithm recomputes the solution from scratch after each update. Furthermore, we prove a quadratic per-update lower bound for unweighted Tree Edit Distance under the k-Clique Conjecture. This provides the first separation between dynamic unweighted String Edit Distance and unweighted Tree Edit Distance, problems whose relative difficulty in the static setting is still open.