TY - GEN

T1 - New and improved algorithms for unordered tree inclusion

AU - Akutsu, Tatsuya

AU - Jansson, Jesper Andreas

AU - Li, Ruiming

AU - Takasu, Atsuhiro

AU - Tamura, Takeyuki

PY - 2018/12/1

Y1 - 2018/12/1

N2 - 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.

AB - 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.

KW - And phrases parameterized algorithms

KW - Dynamic programming

KW - Tree inclusion

KW - Unordered trees

UR - http://www.scopus.com/inward/record.url?scp=85063665830&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.ISAAC.2018.27

DO - 10.4230/LIPIcs.ISAAC.2018.27

M3 - Conference article published in proceeding or book

AN - SCOPUS:85063665830

T3 - Leibniz International Proceedings in Informatics, LIPIcs

SP - 27:1-27:12

BT - 29th International Symposium on Algorithms and Computation, ISAAC 2018

A2 - Lee, Der-Tsai

A2 - Liao, Chung-Shou

A2 - Hsu, Wen-Lian

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 29th International Symposium on Algorithms and Computation, ISAAC 2018

Y2 - 16 December 2018 through 19 December 2018

ER -