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

Ganeshkumar Ganapathy; Tandy Warnow

doi:10.1007/3-540-45753-4_12

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

Ganeshkumar Ganapathy, Tandy Warnow

Research output: Chapter in Book/Report/Conference proceeding › Conference 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(k²n²) 4-approximation algorithm and an O(k²n³) 3-approximation algorithm for the general case of this problem.

Original language	English (US)
Title of host publication	Approximation Algorithms for Combinatorial Optimization - 5th International Workshop, APPROX 2002, Proceedings
Editors	Klaus Jansen, Stefano Leonardi, Vijay Vazirani
Publisher	Springer
Pages	122-134
Number of pages	13
ISBN (Print)	3540441867, 9783540441861
DOIs	https://doi.org/10.1007/3-540-45753-4_12
State	Published - 2002
Externally published	Yes
Event	5th International Workshop On Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2002 - Rome, Italy Duration: Sep 17 2002 → Sep 21 2002

Publication series

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

Other

Other	5th International Workshop On Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2002
Country/Territory	Italy
City	Rome
Period	9/17/02 → 9/21/02

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Online availability

10.1007/3-540-45753-4_12

Library availability

Discover UIUC Full Text

Cite this

Ganapathy, G., & Warnow, T. (2002). Approximating the complement of the maximum compatible subset of leaves of k trees. In K. Jansen, S. Leonardi, & 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. https://doi.org/10.1007/3-540-45753-4_12

Approximating the complement of the maximum compatible subset of leaves of k trees. / Ganapathy, Ganeshkumar; Warnow, Tandy.
Approximation Algorithms for Combinatorial Optimization - 5th International Workshop, APPROX 2002, Proceedings. ed. / Klaus Jansen; Stefano Leonardi; Vijay Vazirani. Springer, 2002. p. 122-134 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2462).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Ganapathy, G & Warnow, T 2002, Approximating the complement of the maximum compatible subset of leaves of k trees. in K Jansen, S Leonardi & V Vazirani (eds), Approximation Algorithms for Combinatorial Optimization - 5th International Workshop, APPROX 2002, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2462, Springer, pp. 122-134, 5th International Workshop On Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2002, Rome, Italy, 9/17/02. https://doi.org/10.1007/3-540-45753-4_12

Ganapathy G, Warnow T. Approximating the complement of the maximum compatible subset of leaves of k trees. In Jansen K, Leonardi S, Vazirani V, editors, Approximation Algorithms for Combinatorial Optimization - 5th International Workshop, APPROX 2002, Proceedings. Springer. 2002. p. 122-134. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-45753-4_12

Ganapathy, Ganeshkumar ; Warnow, Tandy. / Approximating the complement of the maximum compatible subset of leaves of k trees. Approximation Algorithms for Combinatorial Optimization - 5th International Workshop, APPROX 2002, Proceedings. editor / Klaus Jansen ; Stefano Leonardi ; Vijay Vazirani. Springer, 2002. pp. 122-134 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{0783e00ef8434bcdaacaeeba4683c594,

title = "Approximating the complement of the maximum compatible subset of leaves of k trees",

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.",

author = "Ganeshkumar Ganapathy and Tandy Warnow",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2002.; 5th International Workshop On Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2002 ; Conference date: 17-09-2002 Through 21-09-2002",

year = "2002",

doi = "10.1007/3-540-45753-4_12",

language = "English (US)",

isbn = "3540441867",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "122--134",

editor = "Klaus Jansen and Stefano Leonardi and Vijay Vazirani",

booktitle = "Approximation Algorithms for Combinatorial Optimization - 5th International Workshop, APPROX 2002, Proceedings",

address = "Germany",

}

TY - GEN

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

AU - Ganapathy, Ganeshkumar

AU - Warnow, Tandy

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 2002.

PY - 2002

Y1 - 2002

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84956979382&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84956979382&partnerID=8YFLogxK

U2 - 10.1007/3-540-45753-4_12

DO - 10.1007/3-540-45753-4_12

M3 - Conference contribution

AN - SCOPUS:84956979382

SN - 3540441867

SN - 9783540441861

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 122

EP - 134

BT - Approximation Algorithms for Combinatorial Optimization - 5th International Workshop, APPROX 2002, Proceedings

A2 - Jansen, Klaus

A2 - Leonardi, Stefano

A2 - Vazirani, Vijay

PB - Springer

T2 - 5th International Workshop On Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2002

Y2 - 17 September 2002 through 21 September 2002

ER -

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

Abstract

Publication series

Other

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this