Akutsu, Tatsuya ;
Jansson, Jesper ;
Li, Ruiming ;
Takasu, Atsuhiro ;
Tamura, Takeyuki
New and Improved Algorithms for Unordered Tree Inclusion
Abstract
The tree inclusion problem is, given two nodelabeled 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 NPhard. 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 ancestordescendant 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 NPhard 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.
BibTeX  Entry
@InProceedings{akutsu_et_al:LIPIcs:2018:9975,
author = {Tatsuya Akutsu and Jesper Jansson and Ruiming Li and Atsuhiro Takasu and Takeyuki Tamura},
title = {{New and Improved Algorithms for Unordered Tree Inclusion}},
booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)},
pages = {27:127:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770941},
ISSN = {18688969},
year = {2018},
volume = {123},
editor = {WenLian Hsu and DerTsai Lee and ChungShou Liao},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9975},
URN = {urn:nbn:de:0030drops99752},
doi = {10.4230/LIPIcs.ISAAC.2018.27},
annote = {Keywords: parameterized algorithms, tree inclusion, unordered trees, dynamic programming}
}
06.12.2018
Keywords: 

parameterized algorithms, tree inclusion, unordered trees, dynamic programming 
Seminar: 

29th International Symposium on Algorithms and Computation (ISAAC 2018)

Issue date: 

2018 
Date of publication: 

06.12.2018 