The tree edit distance problem is a natural generalization of the classic string edit distance problem. Given two ordered, edge-labeled trees $T_1$ and $T_2$, the edit distance between $T_1$ and $T_2$ is defined as the minimum total cost of operations that transform $T_1$ into $T_2$. In one operation, we can contract an edge, split a vertex into two or change the label of an edge. For the weighted version of the problem, where the cost of each operation depends on the type of the operation and the label on the edge involved, $\mathcal{O}(n^3)$ time algorithms are known for both rooted and unrooted trees. The existence of a truly subcubic $\mathcal{O}(n^{3-\epsilon})$ time algorithm is unlikely, as it would imply a truly subcubic algorithm for the APSP problem. However, recently Mao (FOCS'21) showed that if we assume that each operation has a unit cost, then the tree edit distance between two rooted trees can be computed in truly subcubic time. In this paper, we show how to adapt Mao's algorithm to make it work for unrooted trees and we show an $\widetilde{\mathcal{O}}(n^{(7\omega + 15)/(2\omega + 6)}) \leq \mathcal{O}(n^{2.9417})$ time algorithm for the unweighted tree edit distance between two unrooted trees, where $\omega \leq 2.373$ is the matrix multiplication exponent. It is the first known subcubic algorithm for unrooted trees. The main idea behind our algorithm is the fact that to compute the tree edit distance between two unrooted trees, it is enough to compute the tree edit distance between an arbitrary rooting of the first tree and every rooting of the second tree.
翻译:树编辑距离问题是经典的字符串编辑距离问题的自然推广。给定两个有序的、边标记的树 $T_1$ 和 $T_2$,$T_1$ 和 $T_2$ 之间的编辑距离被定义为将 $T_1$ 转变为 $T_2$ 所需操作的最小总成本。在一次操作中,我们可以收缩一条边,将一个顶点分裂为两个或者改变一条边的标签。对于带权版本的问题,其中每个操作的成本取决于操作的类型和涉及的边上的标签,已知根据不同的树形结构(有根或无根),树编辑距离问题的时间复杂度均为 $\mathcal{O}(n^3)$。真正的子立方 $\mathcal{O}(n^{3-\epsilon})$ 时间复杂度的算法不太可能存在,因为它将意味着求解“所有点对最短路径”(APSP)问题的真正子立方时间复杂度算法存在。然而,最近,Mao (FOCS'21) 显示,如果我们假设每个操作的成本为单位成本,则两个根树之间的树编辑距离可以在真正的子立方时间内计算。在本文中,我们展示了如何调整Mao算法使其适用于无根树,并且我们展示了一种无权无根树编辑距离的 $\widetilde{\mathcal{O}}(n^{(7\omega + 15)/(2\omega + 6)}) \leq \mathcal{O}(n^{2.9417})$ 时间算法,其中 $\omega \leq 2.373$ 是矩阵乘法的指数。它是无根树的第一个已知子立方算法。我们算法的主要思想是:为了计算两个无根树之间的树编辑距离,只需要计算第一棵树的任意根以及第二棵树的每个根之间的树编辑距离即可。