On the complexity of comparing evolutionary trees

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