 When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2018.27
URN: urn:nbn:de:0030-drops-99752
URL: https://drops.dagstuhl.de/opus/volltexte/2018/9975/
 Go to the corresponding LIPIcs Volume Portal

### New and Improved Algorithms for Unordered Tree Inclusion

 pdf-format:

### 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},
DROPS-Home | Fulltext Search | Imprint | Privacy 