hide
Free keywords:
Computer Science, Data Structures and Algorithms, cs.DS
Abstract:
The edit distance between two rooted ordered trees with $n$ nodes labeled
from an alphabet~$\Sigma$ is the minimum cost of transforming one tree into the
other by a sequence of elementary operations consisting of deleting and
relabeling existing nodes, as well as inserting new nodes. Tree edit distance
is a well known generalization of string edit distance. The fastest known
algorithm for tree edit distance runs in cubic $O(n^3)$ time and is based on a
similar dynamic programming solution as string edit distance. In this paper we
show that a truly subcubic $O(n^{3-\varepsilon})$ time algorithm for tree edit
distance is unlikely: For $|\Sigma| = \Omega(n)$, a truly subcubic algorithm
for tree edit distance implies a truly subcubic algorithm for the all pairs
shortest paths problem. For $|\Sigma| = O(1)$, a truly subcubic algorithm for
tree edit distance implies an $O(n^{k-\varepsilon})$ algorithm for finding a
maximum weight $k$-clique.
Thus, while in terms of upper bounds string edit distance and tree edit
distance are highly related, in terms of lower bounds string edit distance
exhibits the hardness of the strong exponential time hypothesis [Backurs, Indyk
STOC'15] whereas tree edit distance exhibits the hardness of all pairs shortest
paths. Our result provides a matching conditional lower bound for one of the
last remaining classic dynamic programming problems.
