TY - JOUR
T1 - The approximability of maximum rooted triplets consistency with fan triplets and forbidden triplets
AU - Dannenberg, Katharina
AU - Jansson, Jesper
AU - Lingas, Andrzej
AU - Lundell, Eva Marta
N1 - Funding Information:
J.J. was partially funded by The Hakubi Project at Kyoto University, Japan, and KAKENHI Grant Number 26330014 . K.D. would like to thank Maciej Liśkiewicz for some valuable discussions related to the problems studied in this paper.
Publisher Copyright:
© 2018 Elsevier B.V.
Copyright:
Copyright 2019 Elsevier B.V., All rights reserved.
PY - 2019/3/31
Y1 - 2019/3/31
N2 - The NP-hard maximum rooted resolved triplets consistency problem (MRTC) takes as input a set S of leaf labels and a set R of resolved triplets over S and asks for a rooted phylogenetic tree that is consistent with the maximum number of elements in R. 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 1∕4-approximation in polynomial time. Next, we generalize Wu's exact exponential-time algorithm for MRTC (Wu, 2004) to MTC. Forcing the algorithm to always output a rooted k-ary phylogenetic tree for any specified k≥2 subsequently leads to an exponential-time approximation scheme (ETAS) for MTC. We then present a polynomial-time approximation scheme (PTAS) for complete instances of MTC (meaning that for every S ′ ⊆S with |S ′ |=3, R contains at least one rooted triplet involving the leaf labels in S ′ ), 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.
AB - The NP-hard maximum rooted resolved triplets consistency problem (MRTC) takes as input a set S of leaf labels and a set R of resolved triplets over S and asks for a rooted phylogenetic tree that is consistent with the maximum number of elements in R. 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 1∕4-approximation in polynomial time. Next, we generalize Wu's exact exponential-time algorithm for MRTC (Wu, 2004) to MTC. Forcing the algorithm to always output a rooted k-ary phylogenetic tree for any specified k≥2 subsequently leads to an exponential-time approximation scheme (ETAS) for MTC. We then present a polynomial-time approximation scheme (PTAS) for complete instances of MTC (meaning that for every S ′ ⊆S with |S ′ |=3, R contains at least one rooted triplet involving the leaf labels in S ′ ), 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.
UR - http://www.scopus.com/inward/record.url?scp=85055904066&partnerID=8YFLogxK
U2 - 10.1016/j.dam.2018.08.028
DO - 10.1016/j.dam.2018.08.028
M3 - Journal articles
AN - SCOPUS:85055904066
SN - 0166-218X
VL - 257
SP - 101
EP - 114
JO - Discrete Applied Mathematics
JF - Discrete Applied Mathematics
ER -
