Document Open Access Logo

Subcubic Algorithm for (Unweighted) Unrooted Tree Edit Distance

Author Krzysztof Pióro

PDF
Thumbnail PDF

File

LIPIcs.ESA.2023.88.pdf
  • Filesize: 0.68 MB
  • 14 pages

Document Identifiers

Author Details

Krzysztof Pióro
  • Jagiellonian University, Kraków, Poland

Acknowledgements

I would like to thank Adam Polak for introducing me to the topic, numerous discussions regarding the problem and his great help in editing this paper.

Cite AsGet BibTex

Krzysztof Pióro. Subcubic Algorithm for (Unweighted) Unrooted Tree Edit Distance. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 88:1-88:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.ESA.2023.88

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algorithm design techniques
Keywords
  • tree edit distance
  • dynamic programming
  • matrix multiplication

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. J. Bellando and R. Kothari. Region-based modeling and tree edit distance as a basis for gesture recognition. In Proceedings 10th International Conference on Image Analysis and Processing, pages 698-703, 1999. URL: https://doi.org/10.1109/ICIAP.1999.797676.
  2. Karl Bringmann, Paweł Gawrychowski, Shay Mozes, and Oren Weimann. Tree edit distance cannot be computed in strongly subcubic time (unless apsp can). ACM Trans. Algorithms, 16(4), July 2020. URL: https://doi.org/10.1145/3381878.
  3. Peter Buneman, Martin Grohe, and Christoph Koch. Path queries on compressed xml. In Proceedings of the 29th International Conference on Very Large Data Bases, pages 141-152. Morgan Kaufmann, 2003. URL: https://doi.org/10.1016/B978-012722442-8/50021-5.
  4. Sudarshan S. Chawathe. Comparing hierarchical data in external memory. In Proceedings of the 25th International Conference on Very Large Data Bases, VLDB '99, pages 90-101, San Francisco, CA, USA, 1999. Morgan Kaufmann Publishers Inc. URL: https://doi.org/10.5555/645925.671669.
  5. Weimin Chen. New algorithm for ordered tree-to-tree correction problem. J. Algorithms, 40(2):135-158, 2001. URL: https://doi.org/10.1006/jagm.2001.1170.
  6. Shucheng Chi, Ran Duan, Tianle Xie, and Tianyi Zhang. Faster min-plus product for monotone instances. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022, pages 1529-1542, New York, NY, USA, 2022. Association for Computing Machinery. URL: https://doi.org/10.1145/3519935.3520057.
  7. Erik D. Demaine, Shay Mozes, Benjamin Rossman, and Oren Weimann. An optimal decomposition algorithm for tree edit distance. ACM Trans. Algorithms, 6(1), December 2010. URL: https://doi.org/10.1145/1644015.1644017.
  8. Bartlomiej Dudek and Pawel Gawrychowski. Edit Distance between Unrooted Trees in Cubic Time. In Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella, editors, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), volume 107 of Leibniz International Proceedings in Informatics (LIPIcs), pages 45:1-45:14, Dagstuhl, Germany, 2018. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.ICALP.2018.45.
  9. Anita Dürr. Improved bounds for rectangular monotone min-plus product and applications. Inf. Process. Lett., 181:106358, 2023. URL: https://doi.org/10.1016/j.ipl.2023.106358.
  10. Paolo Ferragina, Fabrizio Luccio, Giovanni Manzini, and Senthilmurugan Muthukrishnan. Compressing and indexing labeled trees, with applications. J. ACM, 57, November 2009. URL: https://doi.org/10.1145/1613676.1613680.
  11. Matthias Höchsmann, Thomas Töller, Robert Giegerich, and Stefan Kurtz. Local similarity in rna secondary structures. In Computational Systems Bioinformatics. CSB2003. Proceedings of the 2003 IEEE Bioinformatics Conference. CSB2003, pages 159-168, 2003. URL: https://doi.org/10.1109/CSB.2003.1227315.
  12. Philip Klein, Srikanta Tirthapura, Daniel Sharvit, and Ben Kimia. A tree-edit-distance algorithm for comparing simple, closed shapes. In Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '00, pages 696-704, USA, 2000. Society for Industrial and Applied Mathematics. URL: https://doi.org/10.5555/338219.338628.
  13. Philip N. Klein. Computing the edit-distance between unrooted ordered trees. In Gianfranco Bilardi, Giuseppe F. Italiano, Andrea Pietracaprina, and Geppino Pucci, editors, Algorithms - ESA '98, 6th Annual European Symposium, Venice, Italy, August 24-26, 1998, Proceedings, volume 1461 of Lecture Notes in Computer Science, pages 91-102. Springer, 1998. URL: https://doi.org/10.1007/3-540-68530-8_8.
  14. Philip N. Klein, Thomas B. Sebastian, and Benjamin B. Kimia. Shape matching using edit-distance: An implementation. In Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '01, pages 781-790, USA, 2001. Society for Industrial and Applied Mathematics. URL: https://doi.org/10.5555/365411.365779.
  15. Xiao Mao. Breaking the cubic barrier for (unweighted) tree edit distance. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022, pages 792-803. IEEE, 2021. URL: https://doi.org/10.1109/FOCS52979.2021.00082.
  16. Krzysztof Pióro. Subcubic algorithm for (unweighted) unrooted tree edit distance, 2023. URL: https://arxiv.org/abs/2304.08632.
  17. Thomas Sebastian, Philip Klein, and Benjamin Kimia. Recognition of shapes by editing shock graphs. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 26:550-571, June 2004. URL: https://doi.org/10.1109/TPAMI.2004.1273924.
  18. Bruce A. Shapiro and Kaizhong Zhang. Comparing multiple RNA secondary structures using tree comparisons. Bioinformatics, 6(4):309-318, October 1990. URL: https://doi.org/10.1093/bioinformatics/6.4.309.
  19. Kuo-Chung Tai. The tree-to-tree correction problem. J. ACM, 26(3):422-433, July 1979. URL: https://doi.org/10.1145/322139.322143.
  20. Ryan Williams. Faster all-pairs shortest paths via circuit complexity. In Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, STOC '14, pages 664-673, New York, NY, USA, 2014. Association for Computing Machinery. URL: https://doi.org/10.1145/2591796.2591811.
  21. Kaizhong Zhang and Dennis E. Shasha. Simple fast algorithms for the editing distance between trees and related problems. SIAM J. Comput., 18(6):1245-1262, 1989. URL: https://doi.org/10.1137/0218082.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact