Faster Algorithms for Bounded Tree Edit Distance

2021/05/06 by Akmal, Shyan, Jin, Ce · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2105.02428

Abstract

Tree edit distance is a well-studied measure of dissimilarity between rooted trees with node labels. It can be computed in O(n³) time [Demaine, Mozes, Rossman, and Weimann, ICALP 2007], and fine-grained hardness results suggest that the weighted version of this problem cannot be solved in truly subcubic time unless the APSP conjecture is false [Bringmann, Gawrychowski, Mozes, and Weimann, SODA 2018]. We consider the unweighted version of tree edit distance, where every insertion, deletion, or relabeling operation has unit cost. Given a parameter k as an upper bound on the distance, the previous fastest algorithm for this problem runs in O(nk³) time [Touzet, CPM 2005], which improves upon the cubic-time algorithm for k≪ n^2/3. In this paper, we give a faster algorithm taking O(nk² log n) time, improving both of the previous results for almost the full range of log n ≪ k≪ n/√(log n).

Cited by

• Dynamic Dyck and Tree Edit Distance: Decompositions and Reductions to String Edit Distance

Related

• Faster Algorithm for Bounded Tree Edit Distance in the Low-Distance Regime
• Breaking the Cubic Barrier for (Unweighted) Tree Edit Distance
• Faster Weighted and Unweighted Tree Edit Distance and APSP Equivalence
• Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (unless\n APSP can)
• O(n+poly(k))-time Algorithm for Bounded Tree Edit Distance