Search

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 (d 2 2 d m n) 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 (d 2 d m n 2) time, improving the exponential factor from 2 2 d to 2 d 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. • We present an O ⁎ (2 d) -time algorithm for the unordered tree inclusion problem. • This is the first improvement since the O ⁎ (4 d) -time algorithm from 1995 by Kilpeläinen and Mannila. • Even faster algorithms are given for some versions of the problem with restrictions on the node labels and tree heights. • A special case of the problem where only the leaves have distinct labels is proved to be NP-hard. [ABSTRACT FROM AUTHOR]

This article studies the parameterized complexity of the unification problem with associative, commutative, or associative-commutative functions with respect to the parameter “number of variables”. It is shown that if every variable occurs only once then both of the associative and associative-commutative unification problems can be solved in polynomial time, but that in the general case, both problems are W [ 1 ] -hard even when one of the two input terms is variable-free. For commutative unification, an algorithm whose time complexity depends exponentially on the number of variables is presented; moreover, if a certain conjecture is true then the special case where one input term is variable-free belongs to FPT. Some related results are also derived for a natural generalization of the classic string and tree edit distance problems that allows variables. [ABSTRACT FROM AUTHOR]