Abstract:

A coloring of a tree is convex if the vertices that pertain to any
color induce a connected subtree; a partial coloring (which
assigns colors to some of the vertices) is convex if it can be
completed to a convex (total) coloring. Convex (partial) colorings
of trees are closely related to areas such as phylogenetics,
linguistics, etc. (a brief description of these relations will be
given in the talk).

When a coloring of a tree is not convex, it is desirable to know
"how far" it is from a convex one. Few common measures for this are
based on the parsimony score, which is the number of edges whose
endpoints have different colors. In this talk we define and study
another natural measure for this distance: the minimal number of
 vertices which need to be recolored to make the coloring convex.
This can be viewed as minimizing the number of ``exceptional
vertices" w.r.t. to a convex coloring.  We show that finding this
distance is NP-hard even for strings. In the positive side we
present few algorithms for convex recoloring of strings and of trees:
First we present algorithms for optimal convex recolorings of
strings and trees, which runs in $poly(n)exp(c)$ time, where
$n$ is the input size and $c$ is the number of colors.
Then we present algorithms for strings and for trees of bounded
degree, which decide whether the optimal solution is smaller than
$k$ in $poly(n)exp(k)$ time. Finally, we present efficient approximation
algorithms for convex recolorings of strings and trees.  We also
discuss variants of the problem which assume different
cost models.  (Joint work with Sagi Snir).