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

Jesper Andreas Jansson, Andrzej Lingas, Eva Marta Lundell

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

2 Citations (Scopus)

Abstract

The maximum rooted resolved triplets consistency problem takes as input a set R of resolved triplets and asks for a rooted phylogenetic tree that is consistent with the maximum number of elements in R. This paper studies the polynomial-time approximability of a generalization of the problem where in addition to resolved triplets, the input may contain fan triplets and forbidden triplets. To begin with, we observe that the generalized problem admits a 1/4-approximation in polynomial time. Next, we present a polynomial-time approximation scheme (PTAS) for dense instances based on smooth polynomial integer programming. Finally, we generalize Wu’s exact exponential-time algorithm in [19] for the original problem to also allow fan triplets, forbidden resolved triplets, and forbidden fan triplets. Forcing the algorithm to always output a k-ary phylogenetic tree for any specified k ≥ 2 then leads to an exponential-time approximation scheme (ETAS) for the generalized, unrestricted problem.
Original languageEnglish
Title of host publicationCombinatorial Pattern Matching - 26th Annual Symposium, CPM 2015, Proceedings
PublisherSpringer Verlag
Pages272-283
Number of pages12
ISBN (Print)9783319199283
DOIs
Publication statusPublished - 1 Jan 2015
Externally publishedYes
Event26th Annual Symposium on Combinatorial Pattern Matching, CPM 2015 - Ischia Island, Italy
Duration: 29 Jun 20151 Jul 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9133
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference26th Annual Symposium on Combinatorial Pattern Matching, CPM 2015
CountryItaly
CityIschia Island
Period29/06/151/07/15

Keywords

  • Approximation algorithms
  • Bioinformatics
  • Phylogenetic tree
  • Rooted triplet
  • Smooth integer program

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this