M.Sc Thesis | |

M.Sc Student | Feldman Ido |
---|---|

Subject | A 2+Epsilon Approximation Algorithm for Convex Recoloring of Trees |

Department | Department of Computer Science |

Supervisor | PROFESSOR EMERITUS Reuven Bar-Yehuda |

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.