New and improved algorithms for unordered tree inclusion

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

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

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) · 22d) = O(22d) 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(2d). 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.8d) 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.883d)-time algorithm for the case that the heights of P and T are one and two, respectively.

Original languageEnglish
Title of host publication29th International Symposium on Algorithms and Computation, ISAAC 2018
EditorsDer-Tsai Lee, Chung-Shou Liao, Wen-Lian Hsu
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages27:1-27:12
ISBN (Electronic)9783959770941
DOIs
Publication statusPublished - 1 Dec 2018
Event29th International Symposium on Algorithms and Computation, ISAAC 2018 - Jiaoxi, Yilan, Taiwan
Duration: 16 Dec 201819 Dec 2018

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume123
ISSN (Print)1868-8969

Conference

Conference29th International Symposium on Algorithms and Computation, ISAAC 2018
Country/TerritoryTaiwan
CityJiaoxi, Yilan
Period16/12/1819/12/18

Keywords

  • And phrases parameterized algorithms
  • Dynamic programming
  • Tree inclusion
  • Unordered trees

ASJC Scopus subject areas

  • Software

Cite this