The complexity of reconstructing trees from qualitative characters and subtrees (Q1203103)

The author considers the computational complexity of the problem of reconstructing trees from qualitative (taxonomic) characters and subtrees. Recognizing when a consistent parent tree exists is found to be intractable for sets of unrooted trees, even when each tree in the set classifies just four labels. For sets of rooted trees, an algorithm is proposed which enables to build the strict consensus tree of all consistent parent trees (if they exist) in polynomial time. A simple necessary and sufficient condition is given for a set of rooted subtrees to define uniquely a parent tree.