Approximating the complement of the maximum compatible subset of leaves of k trees

Ganeshkumar Ganapathy, Tandy Warnow

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We address a combinatorialprobl em which arises in computationalph ylogenetics. In this problem we are given a set of unrooted (not necessarily binary) trees each leaf-labelled by the same set S, and we wish to remove a minimum number of leaves so that the resultant trees share a common refinement (i.e. they are “compatible”. If we assume the input trees are all binary, then this is simply the Maximum Agreement Subtree problem (MAST), for which much is already known. However, if the input trees need not be binary, then the problem is much more computationally intensive: it is NP-hard for just two trees, and solvable in polynomial time for any number k of trees when all trees have bounded degree. In this paper we present an O(k2n2) 4-approximation algorithm and an O(k2n3) 3-approximation algorithm for the general case of this problem.

Original languageEnglish (US)
Title of host publicationApproximation Algorithms for Combinatorial Optimization - 5th International Workshop, APPROX 2002, Proceedings
EditorsStefano Leonardi, Klaus Jansen, Vijay Vazirani
PublisherSpringer-Verlag
Pages122-134
Number of pages13
ISBN (Print)3540441867, 9783540441861
StatePublished - Jan 1 2002
Externally publishedYes
Event5th International Workshop On Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2002 - Rome, Italy
Duration: Sep 17 2002Sep 21 2002

Publication series

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

Other

Other5th International Workshop On Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2002
CountryItaly
CityRome
Period9/17/029/21/02

    Fingerprint

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Ganapathy, G., & Warnow, T. (2002). Approximating the complement of the maximum compatible subset of leaves of k trees. In S. Leonardi, K. Jansen, & V. Vazirani (Eds.), Approximation Algorithms for Combinatorial Optimization - 5th International Workshop, APPROX 2002, Proceedings (pp. 122-134). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2462). Springer-Verlag.