Tree Edit Distance and Maximum Agreement Subtree

This paper presents an interesting relation between the Maximum Agreement Subtree (MAST) problem and the Tree Edit Distance (TED) problem, both of which have been intensively studied in the literature. To be specific, we show that, for an arbitrary tree edit distance metric that is a derivative of the Tai tree edit distance metric, there exists a MAST-like pattern extraction problem, named Mostly Adjusted Sub-Forest (MASF) problem, such that computing a distance between trees x and y is equivalent to finding an optimal pattern shared between x and y. The MASF problem is different from the MAST problem in: (1) A pattern of the MASF problem may be a forest instead of a tree; (2) Instead of requiring exact match of labels, a pattern of a MASF problem is multi-labeled, and our flexible matching rule only requires that the label set of a vertex of a pattern includes the label of the corresponding vertex in a target tree; (3) To control ambiguity of matching caused by the flexible rule, the objective function includes a penalty function. As an application of this generic framework, we equate the Lu* tree edit distance metric with a pattern extraction problem, named the Mostly Adjusted Agreement Sub-Tree (MAAST) problem. The MAAST problem aims to find optimal agreement subtrees under the flexible matching rule and is solved in O ( n 2 d log ? d ) -time, where n and d are the size and the minimum degree of the input trees. The MAST problem requires O ( n 2.5 ) -time computation. For any derivative of Tai tree edit distance metric, we define a MAST-like problem.Computing distancess for the metric is equivalent to solving the MAST-like problem.Introduce the MAAST problem, which is equivalent to the Lu* distance in this sense.MAAST is a flexible version of MAST, which does not require exact match of labels.The complexities of MAAST are O ( n 2 log ? d ) (unordered) and O ( n 2 ) (ordered).