License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2023.88
URN: urn:nbn:de:0030-drops-187415
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18741/
Pióro, Krzysztof
Subcubic Algorithm for (Unweighted) Unrooted Tree Edit Distance
Abstract
The tree edit distance problem is a natural generalization of the classic string edit distance problem. Given two ordered, edge-labeled trees T₁ and T₂, the edit distance between T₁ and T₂ is defined as the minimum total cost of operations that transform T₁ into T₂. 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, O(n³) time algorithms are known for both rooted and unrooted trees. The existence of a truly subcubic O(n^{3-ε}) 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 Õ(n^{(7ω + 15)/(2ω + 6)}) ≤ O(n^2.9417) time algorithm for the unweighted tree edit distance between two unrooted trees, where ω ≤ 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.
BibTeX - Entry
@InProceedings{pioro:LIPIcs.ESA.2023.88,
author = {Pi\'{o}ro, Krzysztof},
title = {{Subcubic Algorithm for (Unweighted) Unrooted Tree Edit Distance}},
booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)},
pages = {88:1--88:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-295-2},
ISSN = {1868-8969},
year = {2023},
volume = {274},
editor = {G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18741},
URN = {urn:nbn:de:0030-drops-187415},
doi = {10.4230/LIPIcs.ESA.2023.88},
annote = {Keywords: tree edit distance, dynamic programming, matrix multiplication}
}
|
Keywords: |
|
tree edit distance, dynamic programming, matrix multiplication |
|
Collection: |
|
31st Annual European Symposium on Algorithms (ESA 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
30.08.2023 |
