On the complexity of comparing evolutionary trees

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review

171 Scopus Citations
View graph of relations

Author(s)

Detail(s)

Original languageEnglish
Pages (from-to)153-169
Journal / PublicationDiscrete Applied Mathematics
Volume71
Issue number1-3
Publication statusPublished - Dec 1996
Externally publishedYes

Abstract

We study the computational complexity and approximation of several problems arising in the comparison of evolutionary trees. It is shown that the maximum agreement subtree (MAST) problem for three trees with unbounded degree cannot be approximated within ratio 2logδ n in polynomial time for any δ <1, unless NP ⊆ DTIME[2polylog n], and MAST with edge contractions for two binary trees is NP-hard. This answers two open questions posed in [1]. For the maximum refinement subtree (MRST) problem involving two trees, we show that it is polynomial-time solvable when both trees have bounded degree and is NP-hard when one of the trees can have an arbitrary degree. Finally, we consider the problem of optimally transforming a tree into another by transferring subtrees around. It is shown that computing the subtree-transfer distance is NP-hard and an approximation algorithm with performance ratio 3 is given.

Research Area(s)

  • Approximation algorithm, Compatibility, Computational complexity, Evolutionary tree, Phylogeny, Recombination

Citation Format(s)

On the complexity of comparing evolutionary trees. / Hein, Jotun; Jiang, Tao; Wang, Lusheng et al.
In: Discrete Applied Mathematics, Vol. 71, No. 1-3, 12.1996, p. 153-169.

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review