M.Sc Thesis
M.Sc Student Feldman Ido A 2+Epsilon Approximation Algorithm for Convex Recoloring of Trees Department of Computer Science Professor 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.