LIPIcs.ISAAC.2022.44.pdf
- Filesize: 0.71 MB
- 14 pages
Document
On the Complexity of Tree Edit Distance with Variables
Authors
Tatsuya Akutsu 
,
-
Part of:
Volume:
33rd International Symposium on Algorithms and Computation (ISAAC 2022)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Algorithms and Computation (ISAAC) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2022-12-14
File
Document Identifiers
Author Details
Acknowledgements
We are grateful to the members of Sato lab at ATR and Karydo TherapeutiX, Inc. for advice and discussion throughout the course of this work.
Cite As Get BibTex
Tatsuya Akutsu, Tomoya Mori, Naotoshi Nakamura, Satoshi Kozawa, Yuhei Ueno, and Thomas N. Sato. On the Complexity of Tree Edit Distance with Variables. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 44:1-44:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ISAAC.2022.44
Abstract
In this paper, we propose tree edit distance with variables, which is an extension of the tree edit distance to handle trees with variables and has a potential application to measuring the similarity between mathematical formulas. We analyze the computational complexity of several variants of this model. In particular, we show that the problem is NP-complete for ordered trees. We also show for unordered trees that the problem of deciding whether or not the distance is 0 is graph isomorphism complete but can be solved in polynomial time if the maximum outdegree of input trees is bounded by a constant. We also present parameterized and exponential-time algorithms for ordered and unordered cases, respectively.
Subject Classification
ACM Subject Classification
- Theory of computation → Graph algorithms analysis
Keywords
- Tree edit distance
- unification
- parameterized algorithms
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Akiko Aizawa and Michael Kohlhase. Mathematical information retrieval. The Information Retrieval Series (Springer), 43:169-185, 2021. URL: https://doi.org/10.1007/978-981-15-5554-1_12.
- Tatsuya Akutsu. A relation between edit distance for ordered trees and edit distance for Euler strings. Information Process. Letters, 100:105-109, 2006. URL: https://doi.org/10.1016/j.ipl.2006.06.002.
- Tatsuya Akutsu, Jesper Jansson, Atsuhiro Takasu, and Takeyuki Tamura. On the parameterized complexity of associative and commutative unification. Theoretical Computer Science, 660:57-74, 2017. URL: https://doi.org/10.1016/j.tcs.2016.11.026.
- Tatsuya Akutsu, Takeyuki Tamura, Daiji Fukagawa, and Atsuhiro Takasu. Efficient exponential-time algorithms for edit distance between unordered trees. Journal of Discrete Algorithms, 25:79-93, 2014. URL: https://doi.org/10.1016/j.jda.2013.09.001.
- Lázló Babai. Canonical form for graphs in quasipolynomial time: preliminary report. In 51st ACM Symp. Theory of Computing, pages 1237-1246, 2019. URL: https://doi.org/10.1145/3313276.3316356.
- Philip Bille. A survey on tree edit distance and related problems. Theoretical Computer Science, 337:217-239, 2005. URL: https://doi.org/10.1016/j.tcs.2004.12.030.
- Erik D. Demaine, Shay Mozes, Benjamin Rossman, and Oren Weimann. An optimal decomposition algorithm for tree edit distance. ACM Transactions on Algorithms, 6(1):2, 2009. URL: https://doi.org/10.1145/1644015.1644017.
- Xinbo Gao, Bing Xiao, Dacheng Tao, and Xuelong Li. A survey of graph edit distance. Pattern Analysis and Applications, 13:113-129, 2010. URL: https://doi.org/10.1007/s10044-008-0141-y.
- Martin Grohe, Daniel Neuen, and Pascal Schweitzer. A faster isomorphism test for graphs of small degree. In 59th IEEE Symp. Foundations of Computer Science, pages 89-199, 2018. URL: https://doi.org/10.1109/FOCS.2018.00018.
- Shahab Kamali and Frank W. Tompa. A new mathematics retrieval system. In 19th ACM Int. Conf. Information and Knowledge Management, pages 1413-1416, 2010. URL: https://doi.org/10.1145/1871437.1871635.
- Deepak Kapur and Paliath Narendran. Complexity of unification problems with associative-commutative operators. Journal of Automated Reasoning, 9:261-288, 1992. URL: https://doi.org/10.1007/BF00245463.
- Kevin Knight. Unification: a multidisciplinary survey. ACM Computing Surveys, 21:93-124, 1989. URL: https://doi.org/10.1145/62029.62030.
- Eugene M. Luks. Isomorphism of graphs of bounded valence can be tested in polynomial time. Journal of Computer and System Sciences, 25(1):42-65, 1982. URL: https://doi.org/10.1016/0022-0000(82)90009-5.
- Xiao Mao. Breaking the cubic barrier for (unweighted) tree edit distance. In 62nd IEEE Symp. Foundations of Computer Science, pages 792-803, 2021. URL: https://doi.org/10.1109/FOCS52979.2021.00082.
- Tam T. Nguyen, Kuiyu Chang, and Siu Cheung Hu. A math-aware search engine for math question answering system. In 21st ACM Int. Conf. Information and Knowledge Management, pages 724-733, 2012. URL: https://doi.org/10.1145/2396761.2396854.
- Kuo Chung Tai. The tree-to-tree correction problem. Journal of ACM, 26:422-433, 1979. URL: https://doi.org/10.1145/322139.322143.
- Sean T. Vittadello and Michael P. H. Stumpf. Model comparison via simplicial complexes and persistent homology. Royal Society Open Science, 8(10):211361, 2020. URL: https://doi.org/10.1098/rsos.211361.
- Kaizhong Zhang and Dennis Shasha. Simple fast algorithms for the editing distance between trees and related problem. SIAM Journal on Computing, 18:1245-1262, 1989. URL: https://doi.org/10.1137/0218082.
- Kaizhong Zhang, Rick Statman, and Dennis Shasha. On the editing distance between unordered labeled trees. Information Processing Letters, 42:133-139, 1992. URL: https://doi.org/10.1016/0020-0190(92)90136-J.
- Wei Zhong and Richard Zanibbi. Structural similarity search for formulas using leaf-root paths in operator subtrees. In 41st European Conference on IR Research, pages 116-129, 2019. URL: https://doi.org/10.1007/978-3-030-15712-8_8.