FOCS Conference 2025 Conference Paper
- Debarati Das 0001
- Jacob Gilbert
- MohammadTaghi Hajiaghayi
- Tomasz Kociumaka
- Barna Saha
In this paper, we present the first dynamic algorithms for Dyck edit distance and tree edit distance that achieve subpolynomial update times. Dyck edit distance measures how far a parenthesis string is from a wellparenthesized expression (i. e. , the Dyck language), while tree edit distance quantifies the minimum number of node insertions, deletions, and substitutions required to transform one rooted, ordered, and labeled tree into another. These problems have been studied extensively since the 1970s, with recent advances in both algorithmic efficiency and fine-grained complexity lower bounds. Despite this progress, no prior work has addressed efficient dynamic algorithms for these problems, even though many real-world applications involve evolving structured data such as LaTeX, JSON, XML, HTML, hierarchical datasets, and RNA secondary structures. We take the first step in this direction by designing new approximation algorithms for Dyck and tree edit distances in the dynamic setting. Our key technical contribution is a set of novel reduction and decomposition techniques that transform instances of Dyck and tree edit distance into efficiently maintainable instances of string edit distance. Leveraging existing dynamic algorithms for string edit distance, we obtain an $n^{o(1)}$ approximation for Dyck edit distance with $n^{o(1)}$ update time. This builds upon and significantly extends prior work on Dyck language decomposition ([Saha, FOCS’14] and [Koucký & Saks; SODA’23]). For tree edit distance, we introduce a new static reduction that improves the best-known approximation bound from $O\left(n^{3 / 4}\right)$ [Akutsu, Fukagawa, and Takasu; Algorithmica, 2010] to $\tilde{O}(\sqrt{n})$. Moreover, while the previous result was restricted to constant-degree trees, ours holds for arbitrary trees. We then extend our reduction dynamically, yielding a dynamic tree edit distance algorithm with an approximation factor of $n^{1 / 2+o(1)}$ and update time $n^{o(1)}$. A core component of our approach is a new dynamic maintenance algorithm for heavy-light decomposition, a widely used technique in tree algorithms. Given its broad applicability, we believe this result is of independent interest. Finally, we introduce a novel static and dynamic decomposition method that achieves an $\tilde{O}(k)$-approximation for tree edit distance when the tree edit distance is at most k; combined with the trivial bound $k \leq n$, this yields a deterministic $\tilde{O}(\sqrt{n})$-approximation. While similar decompositions exist for strings, no prior work has successfully extended them to trees. Our approach breaks this barrier, improving the best-known approximations for tree edit distance both in the static and dynamic setting. In the static setting, our algorithm runs in $\tilde{O}(n)$ time; in the dynamic setting, it only requires a polylogarithmic worst-case update time. The state-of-the-art near-lineartime static algorithm for tree edit distance previously achieved an $O(\sqrt{n})$-approximation [Boroujeni, Ghodsi, Hajiaghayi, and Seddighin; STOC’19].