Approximation Algorithms for Bounded Degree Phylogenetic Roots

摘要

The Degree-Δ Closest Phylogenetic kth Root Problem (ΔCPR_k) is the problem of finding a (phylogenetic) tree T from a given graph G = (V, E) such that (1) the degree of each internal node in T is at least 3 and at most Δ, (2) the external nodes (i.e. leaves) of T are exactly the elements of V, and (3) the number of disagreements, i.e., |E ⊕ {{u, v) : u,v are leaves of T and d_T(u, v) ≤ k}|, is minimized, where d_T(u, v) denotes the distance between u and v in tree T. This problem arises from theoretical studies in evolutionary biology and generalizes several important combinatorial optimization problems such as the maximum matching problem. Unfortunately, it is known to be NP-hard for all fixed constants Δ, k such that either both Δ ≥ 3 and k ≥ 3, or Δ > 3 and k = 2. This paper presents a polynomial-time 8-approximation algorithm for ΔCPR_2 for any fixed Δ > 3, a quadratic-time 12-approximation algorithm for 3CPR3, and a polynomial-time approximation scheme for the maximization version of ΔCPR_k for any fixed Δ and k.