2017/12/15 by Tatsuya Akutsu, Jesper Jansson, Akutsu, Tatsuya +7
Computer Science · #Algorithms and Data Compression #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1712.05517
openalex publication_date 2017/12/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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(22d mn) 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(2d mn2) 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.