Rooted maximum agreement supertrees

Jesper Andreas Jansson, Joseph H K Ng, Kunihiko Sadakane, Wing Kin Sung

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

36 Citations (Scopus)

Abstract

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.
Original languageEnglish
Title of host publicationLATIN 2004: Theoretical Informatics, 6th Latin American Syposium, Buenos Aires, Argentina, April 2004 Proceedings
EditorsMartin Farach-Colton
Pages499-508
Number of pages10
DOIs
Publication statusPublished - 2004
Externally publishedYes
Event6th Latin American Symposium on Theoretical Informatics, LATIN 2004 - Buenos Aires, Argentina
Duration: 5 Apr 20048 Apr 2004

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherSpringer Verlag
VolumeLNCS 2976
ISSN (Electronic)0302-9743

Conference

Conference6th Latin American Symposium on Theoretical Informatics, LATIN 2004
Country/TerritoryArgentina
CityBuenos Aires
Period5/04/048/04/04

Keywords

  • Algorithm
  • Computational complexity
  • Maximum agreement supertree
  • Phylogenetic tree
  • Rooted triplet

ASJC Scopus subject areas

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Cite this