Abstract
Given a graph G = (V, E) and two positive integers k and Delta, the Delta-closest phylogenetic k-th root problem (Delta CPRk) is to find a (phylogenetic) tree T such that the degree of each internal node in T is at least three and at most Delta, the external nodes of T are exactly the elements of V, and the number of "k-disagreements" is minimized. In this paper we give an approximation algorithm for Delta CPR2 for any fixed Delta > 3. The expected ratio of our algorithm is 3, if there is no vertex with degree more than Delta - 2, and Delta + 2, otherwise, which improves the best known previous ratio of 8 for Delta <= 5.