The complexity of inferring a minimally resolved phylogenetic supertree
(2012) In SIAM Journal on Computing 41(1). p.272291 Abstract
 A recursive algorithm by Aho et al. [SIAM J. Comput., 10 (1981), pp. 405421] forms the basis for many modern rooted supertree methods employed in Phylogenetics. However, as observed by Bryant [Building Trees, Hunting for Trees, and Comparing Trees: Theory and Methods in Phylogenetic Analysis, Ph.D. thesis, University of Canterbury, Christchurch, New Zealand, 1997], the tree output by the algorithm of Aho et al. is not always minimal; there may exist other trees which contain fewer nodes yet are still consistent with the input. In this paper, we prove strong polynomialtime inapproximability results for the problem of inferring a minimally resolved supertree from a given consistent set of rooted triplets (MINRS). Furthermore, we show that... (More)
 A recursive algorithm by Aho et al. [SIAM J. Comput., 10 (1981), pp. 405421] forms the basis for many modern rooted supertree methods employed in Phylogenetics. However, as observed by Bryant [Building Trees, Hunting for Trees, and Comparing Trees: Theory and Methods in Phylogenetic Analysis, Ph.D. thesis, University of Canterbury, Christchurch, New Zealand, 1997], the tree output by the algorithm of Aho et al. is not always minimal; there may exist other trees which contain fewer nodes yet are still consistent with the input. In this paper, we prove strong polynomialtime inapproximability results for the problem of inferring a minimally resolved supertree from a given consistent set of rooted triplets (MINRS). Furthermore, we show that the decision version of MINRS is NPhard for any fixed positive integer q >= 4, where q is the number of allowed internal nodes, but lineartime solvable for q <= 3. In contrast, MINRS becomes polynomialtime solvable for any q when restricted to caterpillars. We also present an exponentialtime algorithm based on tree separators for solving MINRS exactly. It runs in 2(O(n log p)) time when every node may have at most p children that are internal nodes and where n is the cardinality of the leaf label set. Finally, we demonstrate that augmenting the algorithm of Aho et al. with an algorithm for optimal graph coloring to help merge certain blocks of leaves during the execution does not improve the output solution much in the worst case. (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/record/2517538
 author
 Jansson, Jesper; Lemence, Richard S. and Lingas, Andrzej ^{LU}
 organization
 publishing date
 2012
 type
 Contribution to journal
 publication status
 published
 subject
 keywords
 tree separator, graph coloring, NPhardness, minimally resolved supertree, rooted triplet, phylogenetic tree
 in
 SIAM Journal on Computing
 volume
 41
 issue
 1
 pages
 272  291
 publisher
 SIAM Publications
 external identifiers

 wos:000300892300012
 scopus:84861639410
 ISSN
 00975397
 DOI
 10.1137/100811489
 language
 English
 LU publication?
 yes
 id
 68624f9532cf45be8f98aaf5803e9b0f (old id 2517538)
 date added to LUP
 20120515 07:21:22
 date last changed
 20170521 03:48:11
@article{68624f9532cf45be8f98aaf5803e9b0f, abstract = {A recursive algorithm by Aho et al. [SIAM J. Comput., 10 (1981), pp. 405421] forms the basis for many modern rooted supertree methods employed in Phylogenetics. However, as observed by Bryant [Building Trees, Hunting for Trees, and Comparing Trees: Theory and Methods in Phylogenetic Analysis, Ph.D. thesis, University of Canterbury, Christchurch, New Zealand, 1997], the tree output by the algorithm of Aho et al. is not always minimal; there may exist other trees which contain fewer nodes yet are still consistent with the input. In this paper, we prove strong polynomialtime inapproximability results for the problem of inferring a minimally resolved supertree from a given consistent set of rooted triplets (MINRS). Furthermore, we show that the decision version of MINRS is NPhard for any fixed positive integer q >= 4, where q is the number of allowed internal nodes, but lineartime solvable for q <= 3. In contrast, MINRS becomes polynomialtime solvable for any q when restricted to caterpillars. We also present an exponentialtime algorithm based on tree separators for solving MINRS exactly. It runs in 2(O(n log p)) time when every node may have at most p children that are internal nodes and where n is the cardinality of the leaf label set. Finally, we demonstrate that augmenting the algorithm of Aho et al. with an algorithm for optimal graph coloring to help merge certain blocks of leaves during the execution does not improve the output solution much in the worst case.}, author = {Jansson, Jesper and Lemence, Richard S. and Lingas, Andrzej}, issn = {00975397}, keyword = {tree separator,graph coloring,NPhardness,minimally resolved supertree,rooted triplet,phylogenetic tree}, language = {eng}, number = {1}, pages = {272291}, publisher = {SIAM Publications}, series = {SIAM Journal on Computing}, title = {The complexity of inferring a minimally resolved phylogenetic supertree}, url = {http://dx.doi.org/10.1137/100811489}, volume = {41}, year = {2012}, }