Advanced

The approximability of maximum rooted triplets consistency with fan triplets and forbidden triplets

Dannenberg, Katharina; Jansson, Jesper LU ; Lingas, Andrzej LU and Lundell, Eva Marta LU (2018) In Discrete Applied Mathematics
Abstract

The NP-hard 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 exponential-time... (More)

The NP-hard 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 exponential-time 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 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 [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)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
epub
subject
keywords
Approximation algorithm, Dynamic programming, Phylogenetic tree, Rooted triplet, Smooth polynomial integer program
in
Discrete Applied Mathematics
publisher
Elsevier
external identifiers
  • scopus:85055904066
ISSN
0166-218X
DOI
10.1016/j.dam.2018.08.028
language
English
LU publication?
yes
id
17e6f394-83f3-4812-a9a2-bd3197942552
date added to LUP
2018-11-22 09:40:08
date last changed
2019-01-06 14:16:36
@article{17e6f394-83f3-4812-a9a2-bd3197942552,
  abstract     = {<p>The NP-hard 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 exponential-time 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 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 [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         = {0166-218X},
  keyword      = {Approximation algorithm,Dynamic programming,Phylogenetic tree,Rooted triplet,Smooth polynomial integer program},
  language     = {eng},
  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},
  year         = {2018},
}