Affordable Access

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

University of Canterbury. Mathematics and Statistics.
Publication Date
  • Phylogenetic Trees
  • Compatibility
  • Np-Complete
  • Probability
  • Reconstruction
  • Fields Of Research::230000 Mathematical Sciences::239900 Other Mathematical Sciences::239901 Biologi
  • Computer Science


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.

There are no comments yet on this publication. Be the first to share your thoughts.


Seen <100 times