# Technical Report MSC-2006-10

 TR#: MSC-2006-10 Class: MSC Title: 2+epsilon approximation algorithm for convex recoloring of trees Authors: Ido Feldman Supervisors: Reuven Bar-Yehuda PDF MSC-2006-10.pdf Abstract: A coloring of a tree is \emph{convex} if for any two vertices $u$ and $v$ that are colored by the same color $c$, every vertex on the path from $u$ to $v$ is also colored by $c$. That is, the vertices that are colored with the same color induce a subtree. Given a weight function on the vertices of the tree the \emph{recoloring distance} of a recoloring is the total weight of recolored vertices. In the \emph{minimum convex recoloring problem} we are given a colored tree and a weight function and our goal is to find a convex recoloring of minimum recoloring distance. The minimum convex recoloring problem naturally arises in the context of \emph{phylogenetic trees}. Given a set of related species the goal of phylogenetic reconstruction is to construct a tree that would best describe the evolution of this set of species. In this context a convex coloring correspond to \emph{perfect phylogeny}. Since perfect phylogeny is not always possible the next best thing is to find a tree which is as close to convex as possible, or, in other words, a tree with minimum recoloring distance. We present a $(2+\eps)$-approximation algorithm for the minimum convex recoloring problem, whose running time is $O(n^2+ (1/\eps)^2 4^{1/\eps})$. This result improves the previously known $3$-approximation algorithm for this NP-hard problem. Copyright The above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/2006/MSC/MSC-2006-10), rather than to the URL of the PDF files directly. The latter URLs may change without notice.