Faster Algorithms for Bounded Tree Edit Distance
share
Tree edit distance is a well-studied measure of dissimilarity between rooted trees with node labels. It can be computed in O(n^3) 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^3) 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^2 log n) time, improving both of the previous results for almost the full range of log n ≪ k≪ n/√(log n).
READ FULL TEXT