| TR#: | MSC-2006-10 |
| Class: | MSC |
| Title: | 2+epsilon approximation algorithm for convex recoloring of trees |
| Authors: | Ido Feldman |
| Supervisors: | Reuven Bar-Yehuda |
| 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 or PS 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