Ng, Meei PyngSteel, M.Wormald, N.2016-08-142016-08-1419951172-8531http://hdl.handle.net/10092/12577Given 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 NPcomplete 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. 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.enAll Rights Reservedphylogenetic treescompatibilityNP-completeprobabilityreconstructionDiscussion / Working PapersFields of Research::49 - Mathematical sciences::4901 - Applied mathematics::490102 - Biological mathematics