Technical Report MSC-2006-10

Title: 2+epsilon approximation algorithm for convex recoloring of trees
Authors: Ido Feldman
Supervisors: Reuven Bar-Yehuda
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.

CopyrightThe 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 (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2006
To the main CS technical reports page

Computer science department, Technion