New and improved algorithms for unordered tree inclusion

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

Research output: Journal article publicationJournal articleAcademic researchpeer-review

Abstract

The tree inclusion problem is, given two node-labeled trees P and T (the “pattern tree” and the “target 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 a classic algorithm by Kilpeläinen and Mannila from 1995 that runs in O(d22dmn) time, where m and n are the sizes of the pattern and target trees, respectively, and d is the degree of the pattern tree. Here, we develop a new algorithm that runs in O(d2dmn2) time, improving the exponential factor from 22d to 2d by considering a particular type of ancestor-descendant relationships that is suitable for dynamic programming. We also study restricted variants of the unordered tree inclusion problem.

Original languageEnglish
Pages (from-to)83-98
Number of pages16
JournalTheoretical Computer Science
Volume883
DOIs
Publication statusPublished - 2021

Keywords

  • Dynamic programming
  • Parameterized algorithms
  • Tree inclusion
  • Unordered trees

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this