Finding a Largest Subset of Rooted Triples Identifying a Tree is an NP-hard task - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Reports Year : 2007

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

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.
Fichier principal
Vignette du fichier
Ranwez_et_al_April07_main-ModifsNonVisibles.pdf (447.49 Ko) Télécharger le fichier
Loading...

Dates and versions

lirmm-00143208 , version 1 (24-04-2007)

Identifiers

  • HAL Id : lirmm-00143208 , version 1

Cite

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⟩
189 View
93 Download

Share

Gmail Facebook X LinkedIn More