The approximability of maximum rooted triplets consistency with fan triplets and forbidden triplets
(2019) In Discrete Applied Mathematics 257. p.101114 Abstract
The NPhard maximum rooted resolved triplets consistency problem (MRTC) takes as input a set [Formula presented] of leaf labels and a set [Formula presented] of resolved triplets over [Formula presented] and asks for a rooted phylogenetic tree that is consistent with the maximum number of elements in [Formula presented]. This article studies the approximability of a generalization of the problem called the maximum rooted triplets consistency problem (MTC) where in addition to resolved triplets, the input may contain fan triplets, forbidden resolved triplets, and forbidden fan triplets. To begin with, we observe that MTC admits a [Formula presented]approximation in polynomial time. Next, we generalize Wu's exact exponentialtime... (More)
The NPhard maximum rooted resolved triplets consistency problem (MRTC) takes as input a set [Formula presented] of leaf labels and a set [Formula presented] of resolved triplets over [Formula presented] and asks for a rooted phylogenetic tree that is consistent with the maximum number of elements in [Formula presented]. This article studies the approximability of a generalization of the problem called the maximum rooted triplets consistency problem (MTC) where in addition to resolved triplets, the input may contain fan triplets, forbidden resolved triplets, and forbidden fan triplets. To begin with, we observe that MTC admits a [Formula presented]approximation in polynomial time. Next, we generalize Wu's exact exponentialtime algorithm for MRTC (Wu, 2004) to MTC. Forcing the algorithm to always output a rooted [Formula presented]ary phylogenetic tree for any specified [Formula presented] subsequently leads to an exponentialtime approximation scheme (ETAS) for MTC. We then present a polynomialtime approximation scheme (PTAS) for complete instances of MTC (meaning that for every [Formula presented] with [Formula presented], [Formula presented] contains at least one rooted triplet involving the leaf labels in [Formula presented]), based on the techniques introduced by Jiang et al. (2001) for a related problem. We also study the computational complexity of MTC restricted to fan triplets and forbidden fan triplets. Finally, extensions to weighted instances are considered.
(Less)
 author
 Dannenberg, Katharina ; Jansson, Jesper ^{LU} ; Lingas, Andrzej ^{LU} and Lundell, Eva Marta ^{LU}
 organization
 publishing date
 2019
 type
 Contribution to journal
 publication status
 published
 subject
 keywords
 Approximation algorithm, Dynamic programming, Phylogenetic tree, Rooted triplet, Smooth polynomial integer program
 in
 Discrete Applied Mathematics
 volume
 257
 pages
 101  114
 publisher
 Elsevier
 external identifiers

 scopus:85055904066
 ISSN
 0166218X
 DOI
 10.1016/j.dam.2018.08.028
 language
 English
 LU publication?
 yes
 id
 17e6f39483f34812a9a2bd3197942552
 date added to LUP
 20181122 09:40:08
 date last changed
 20200113 01:12:19
@article{17e6f39483f34812a9a2bd3197942552, abstract = {<p>The NPhard maximum rooted resolved triplets consistency problem (MRTC) takes as input a set [Formula presented] of leaf labels and a set [Formula presented] of resolved triplets over [Formula presented] and asks for a rooted phylogenetic tree that is consistent with the maximum number of elements in [Formula presented]. This article studies the approximability of a generalization of the problem called the maximum rooted triplets consistency problem (MTC) where in addition to resolved triplets, the input may contain fan triplets, forbidden resolved triplets, and forbidden fan triplets. To begin with, we observe that MTC admits a [Formula presented]approximation in polynomial time. Next, we generalize Wu's exact exponentialtime algorithm for MRTC (Wu, 2004) to MTC. Forcing the algorithm to always output a rooted [Formula presented]ary phylogenetic tree for any specified [Formula presented] subsequently leads to an exponentialtime approximation scheme (ETAS) for MTC. We then present a polynomialtime approximation scheme (PTAS) for complete instances of MTC (meaning that for every [Formula presented] with [Formula presented], [Formula presented] contains at least one rooted triplet involving the leaf labels in [Formula presented]), based on the techniques introduced by Jiang et al. (2001) for a related problem. We also study the computational complexity of MTC restricted to fan triplets and forbidden fan triplets. Finally, extensions to weighted instances are considered.</p>}, author = {Dannenberg, Katharina and Jansson, Jesper and Lingas, Andrzej and Lundell, Eva Marta}, issn = {0166218X}, language = {eng}, pages = {101114}, publisher = {Elsevier}, series = {Discrete Applied Mathematics}, title = {The approximability of maximum rooted triplets consistency with fan triplets and forbidden triplets}, url = {http://dx.doi.org/10.1016/j.dam.2018.08.028}, doi = {10.1016/j.dam.2018.08.028}, volume = {257}, year = {2019}, }