The difficulty of constructing a leaf-labelled tree including or avoiding given subtrees Original Research Article

Given a set of trees with leaves labelled from a set L, is there a tree T with leaves labelled by L such that each of the given trees is homeomorphic to a subtree of T? This question is known to be NP-complete in general, but solvable in polynomial time if all the given trees have one label in common (equivalently, if the given trees are rooted). Here we show that this problem is NP-complete even if there are two labels x and y such that each given tree contains x or y. However, if it is known that the distance between x and y is less than 4, then the problem is solvable in polynomial time. We give an algorithm for doing this. On the other hand, we show that the question of whether a fully resolved (binary) tree exists which has no subtree homeomorphic to one of the given ones is NP-complete, even when the given trees are rooted. This sheds some light on the complexity of determining whether a probability assignment to trees is coherent.