Skip to Main content Skip to Navigation

Finding a Largest Subset of Rooted Triples Identifying a Tree is an NP-hard task

Sylvain Guillemot 1 Vincent Berry 1
1 MAB - Méthodes et Algorithmes pour la Bioinformatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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.
Complete list of metadata

Cited literature [58 references]  Display  Hide  Download
Contributor : Vincent Berry <>
Submitted on : Tuesday, April 24, 2007 - 4:13:35 PM
Last modification on : Thursday, May 24, 2018 - 3:59:22 PM
Long-term archiving on: : Wednesday, April 7, 2010 - 3:25:42 AM


  • HAL Id : lirmm-00143208, version 1



Sylvain Guillemot, Vincent Berry. Finding a Largest Subset of Rooted Triples Identifying a Tree is an NP-hard task. RR-07010, 2007, pp.7. ⟨lirmm-00143208⟩



Record views


Files downloads