Abstract
Supertree methods are used to build comprehensive phylogenies from source trees with overlapping sets of leaves. Ranwez et al (2007) recently proposed a polynomial-time method outputting supertrees that verify attractive mathematical properties to obtain a consensual summary of a collection of source trees. The topological information of the source trees that is considered by the method is the set of rooted triples they define on the leaf set. The method finds a subset of these rooted triples that identify a supertree and return the corresponding supertree. Biologists are interested in supertrees that are as resolved as possible. Thus, given a set of rooted triples on a set of taxa, Ranwez et al (2007) asked whether it is possible to find in polynomial time a largest subset of rooted triples identifying a tree. In this short note, we show that solving this problem is an NP-hard task.