License
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://drops.dagstuhl.de/opus/volltexte/2018/9975/
Go to the corresponding LIPIcs Volume Portal


Akutsu, Tatsuya ; Jansson, Jesper ; Li, Ruiming ; Takasu, Atsuhiro ; Tamura, Takeyuki

New and Improved Algorithms for Unordered Tree Inclusion

pdf-format:
LIPIcs-ISAAC-2018-27.pdf (0.5 MB)


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
Seminar: 29th International Symposium on Algorithms and Computation (ISAAC 2018)
Issue Date: 2018
Date of publication: 27.11.2018


DROPS-Home | Imprint | Privacy Published by LZI