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.
Liste complète des métadonnées

Littérature citée [58 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00143208
Contributeur : Vincent Berry <>
Soumis le : mardi 24 avril 2007 - 16:13:35
Dernière modification le : jeudi 24 mai 2018 - 15:59:22
Document(s) archivé(s) le : mercredi 7 avril 2010 - 03:25:42

Identifiants

  • HAL Id : lirmm-00143208, version 1

Collections

Citation

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〉

Partager

Métriques

Consultations de la notice

295

Téléchargements de fichiers

101