2026-08-17T16:11:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9975 2024-03-06T10:45:14Z ddc:004 open_access

New and Improved Algorithms for Unordered Tree Inclusion Akutsu, Tatsuya Jansson, Jesper Li, Ruiming Takasu, Atsuhiro Tamura, Takeyuki parameterized algorithms tree inclusion unordered trees dynamic programming The tree inclusion problem is, given two node-labeled trees P and T (the "pattern tree" and the "text tree"), to locate every minimal subtree in T (if any) that can be obtained by applying a sequence of node insertion operations to P. Although the ordered tree inclusion problem is solvable in polynomial time, the unordered tree inclusion problem is NP-hard. The currently fastest algorithm for the latter is from 1995 and runs in O(poly(m,n) * 2^{2d}) = O^*(2^{2d}) time, where m and n are the sizes of the pattern and text trees, respectively, and d is the maximum outdegree of the pattern tree. Here, we develop a new algorithm that improves the exponent 2d to d by considering a particular type of ancestor-descendant relationships and applying dynamic programming, thus reducing the time complexity to O^*(2^d). We then study restricted variants of the unordered tree inclusion problem where the number of occurrences of different node labels and/or the input trees' heights are bounded. We show that although the problem remains NP-hard in many such cases, it can be solved in polynomial time for c = 2 and in O^*(1.8^d) time for c = 3 if the leaves of P are distinctly labeled and each label occurs at most c times in T. We also present a randomized O^*(1.883^d)-time algorithm for the case that the heights of P and T are one and two, respectively. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tatsuya Akutsu and Jesper Jansson and Ruiming Li and Atsuhiro Takasu and Takeyuki Tamura 2018 Is Part Of LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2018.27 urn:nbn:de:0030-drops-99752 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.27 eng https://creativecommons.org/licenses/by/3.0/legalcode