Optimizing tree and character compatibility across several phylogenetic trees

Given a set RR of rooted phylogenetic trees on overlapping taxa, it takes polynomial time to decide whether or not there exists a rooted phylogenetic tree that is compatible with RR. Since not all evolutionary histories for a set of species can be explained by a single tree, it is natural to ask for the minimum number of rooted phylogenetic trees needed such that each tree in RR is compatible with at least one tree. This paper shows that it is computationally hard to compute this minimum number. In particular, if RR contains rooted triples (rooted binary phylogenetic trees on three leaves), it is NP-complete to decide whether there exist two rooted phylogenetic trees such that each rooted triple in RR is compatible with at least one of the two trees. Furthermore, for a set Σ of binary characters and a positive integer k  , we show that to decide if there exists a set PP of k rooted phylogenetic trees such that each character in Σ   is compatible with at least one tree in PP is NP-complete for all k⩾3k⩾3, but solvable in polynomial time for k=2k=2. This generalizes the result for k=1k=1, where it is well-known to be polynomial time.