Approximation algorithms for bounded degree phylogenetic roots

The DEGREE-Delta CLOSEST PHYLOGENETIC kTH ROOT PROBLEM (Delta CPRk) 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 circle plus{{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 Delta, k such that either both Delta >= 3 and k >= 3, or Delta > 3 and k = 2. This paper presents a polynomial-time 8-approximation algorithm for Delta CPR2 for any fixed Delta > 3, a quadratic-time 12-approximation algorithm for 3CPR(3), and a polynomial-time approximation scheme for the maximization version of Delta CPRk for any fixed. and k.