TY - GEN
T1 - Rooted maximum agreement supertrees
AU - Jansson, Jesper Andreas
AU - Ng, Joseph H K
AU - Sadakane, Kunihiko
AU - Sung, Wing Kin
PY - 2004
Y1 - 2004
N2 - Given a set τ rooted, unordered trees, where each Ti ∈ τ is distinctly leaf-labeled by a set Λ(Ti) and where the sets Λ(Ti) may overlap, the maximum agreement supertree problem(MASP) is to construct a distinctly leaf-labeled tree script Q sign with leaf set Λ(script Q sign) ⊆ ∪Ti ∈ τ Λ(Ti) such that |Λ(script Q sign)| is maximized and for each Ti ∈ Τ, the topological restriction of Ti to Λ(script Q sign) is isomorphic to the topological restriction of script Q sign to Λ(Ti). Let n = |∪Ti ∈ τ Λ(Ti)|, k = |Τ|, and D = maxTi ∈ Τ {deg(Ti)}. We first show that MASP with k = 2 can be solved in O(√Dn log (2n/D)) time, which is O(n log n) when D = O(1) and O(n 1.5) when D is unrestricted. We then present an algorithm for MASP with D = 2 whose running time is polynomial if k = O(1). On the other hand, we prove that MASP is NP-hard for any fixed k ≥ 3 when D is unrestricted, and also NP-hard for any fixed D ≥ 2 when k is unrestricted even if each input tree is required to contain at most three leaves. Finally, we describe a polynomial-time (n/log n)-approximation algorithm for MASP.
AB - Given a set τ rooted, unordered trees, where each Ti ∈ τ is distinctly leaf-labeled by a set Λ(Ti) and where the sets Λ(Ti) may overlap, the maximum agreement supertree problem(MASP) is to construct a distinctly leaf-labeled tree script Q sign with leaf set Λ(script Q sign) ⊆ ∪Ti ∈ τ Λ(Ti) such that |Λ(script Q sign)| is maximized and for each Ti ∈ Τ, the topological restriction of Ti to Λ(script Q sign) is isomorphic to the topological restriction of script Q sign to Λ(Ti). Let n = |∪Ti ∈ τ Λ(Ti)|, k = |Τ|, and D = maxTi ∈ Τ {deg(Ti)}. We first show that MASP with k = 2 can be solved in O(√Dn log (2n/D)) time, which is O(n log n) when D = O(1) and O(n 1.5) when D is unrestricted. We then present an algorithm for MASP with D = 2 whose running time is polynomial if k = O(1). On the other hand, we prove that MASP is NP-hard for any fixed k ≥ 3 when D is unrestricted, and also NP-hard for any fixed D ≥ 2 when k is unrestricted even if each input tree is required to contain at most three leaves. Finally, we describe a polynomial-time (n/log n)-approximation algorithm for MASP.
KW - Algorithm
KW - Computational complexity
KW - Maximum agreement supertree
KW - Phylogenetic tree
KW - Rooted triplet
UR - https://www.scopus.com/record/display.uri?eid=2-s2.0-21144433769&origin=resultslist&sort=plf-f&src=s&sid=34de6aa52b629d27e2b3e66852e1b01b&sot=autdocs&sdt=autdocs&sl=18&s=AU-ID%2810439175200%29&relpos=98&citeCnt=6&searchTerm=
U2 - 10.1007/s00453-004-1147-5
DO - 10.1007/s00453-004-1147-5
M3 - Conference article published in proceeding or book
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 499
EP - 508
BT - LATIN 2004: Theoretical Informatics, 6th Latin American Syposium, Buenos Aires, Argentina, April 2004 Proceedings
A2 - Farach-Colton, Martin
T2 - 6th Latin American Symposium on Theoretical Informatics, LATIN 2004
Y2 - 5 April 2004 through 8 April 2004
ER -