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

Meei Pyng Ng, Mike Steel, Nicholas C. Wormald

Research output: Contribution to journalArticleResearchpeer-review

10 Citations (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)227-235
Number of pages9
JournalDiscrete Applied Mathematics
Volume98
Issue number3
Publication statusPublished - 15 Jan 2000
Externally publishedYes

Keywords

  • Compatibility
  • NP-complete
  • Phylogenetic trees
  • Probability
  • Reconstruction

Cite this