Document Open Access Logo

On the Complexity of Tree Edit Distance with Variables

Authors Tatsuya Akutsu , Tomoya Mori, Naotoshi Nakamura, Satoshi Kozawa, Yuhei Ueno, Thomas N. Sato

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2022.44.pdf
  • Filesize: 0.71 MB
  • 14 pages

Document Identifiers

Author Details

Tatsuya Akutsu
  • Bioinformatics Center, Institute for Chemical Research, Kyoto University, Japan
Tomoya Mori
  • Bioinformatics Center, Institute for Chemical Research, Kyoto University, Japan
Naotoshi Nakamura
  • The Thomas N. Sato BioMEC-X Laboratories, Advanced Telecommunications Research Institute International (ATR), Kyoto, Japan
  • Karydo TherapeutiX, Inc., Tokyo, Japan
  • Interdisciplinary Biology Laboratory (iBLab), Division of Natural Science, Graduate School of Science, Nagoya University, Japan
Satoshi Kozawa
  • The Thomas N. Sato BioMEC-X Laboratories, Advanced Telecommunications Research Institute International (ATR), Kyoto, Japan
  • Karydo TherapeutiX, Inc., Tokyo, Japan
Yuhei Ueno
  • The Thomas N. Sato BioMEC-X Laboratories, Advanced Telecommunications Research Institute International (ATR), Kyoto, Japan
  • Karydo TherapeutiX, Inc., Tokyo, Japan
  • V-iCliniX Laboratory, Nara Medical University, Japan
Thomas N. Sato
  • The Thomas N. Sato BioMEC-X Laboratories, Advanced Telecommunications Research Institute International (ATR), Kyoto, Japan
  • Karydo TherapeutiX, Inc., Tokyo, Japan
  • V-iCliniX Laboratory, Nara Medical University, Japan

Funding

  • Akutsu, Tatsuya: Partially supported by JSPS KAKENHI #JP22H00532 and #JP22K19830.
  • Nakamura, Naotoshi: Partially supported by JSPS KAKENHI #JP17H06003 and #JP19H05422.
  • Sato, Thomas N.: Partially supported by JST ERATO Grant Number JPMJER1303, Nakatani Foundation, and AMED under Grant Number JP21he2102002.

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 AsGet 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)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. 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.
  7. 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.
  8. 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.
  9. 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.
  10. 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.
  11. 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.
  12. Kevin Knight. Unification: a multidisciplinary survey. ACM Computing Surveys, 21:93-124, 1989. URL: https://doi.org/10.1145/62029.62030.
  13. 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.
  14. 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.
  15. 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.
  16. Kuo Chung Tai. The tree-to-tree correction problem. Journal of ACM, 26:422-433, 1979. URL: https://doi.org/10.1145/322139.322143.
  17. 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.
  18. 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.
  19. 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.
  20. 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.
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