License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2018.27
URN: urn:nbn:de:0030-drops-99752
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9975/
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 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.
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:1--27:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-094-1},
ISSN = {1868-8969},
year = {2018},
volume = {123},
editor = {Wen-Lian Hsu and Der-Tsai Lee and Chung-Shou Liao},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9975},
URN = {urn:nbn:de:0030-drops-99752},
doi = {10.4230/LIPIcs.ISAAC.2018.27},
annote = {Keywords: parameterized algorithms, tree inclusion, unordered trees, dynamic programming}
}
|
Keywords: |
|
parameterized algorithms, tree inclusion, unordered trees, dynamic programming |
|
Collection: |
|
29th International Symposium on Algorithms and Computation (ISAAC 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
06.12.2018 |
