  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 coloring of trees arise in areas such as phylogenetics, linguistics,
etc. eg, a perfect phylogenetic tree is one in which the states of each
character induce a convex coloring of the tree. Research on perfect phylogeny
is usually focused on finding a tree so that few predetermined partial
colorings of its vertices are convex.
  When a coloring of a tree is not convex, it is desirable to know "how far" it
is from a convex one. In [19], a natural measure for this distance, called the
recoloring distance was defined: the minimal number of color changes at the
vertices needed to make the coloring convex. This can be viewed as minimizing
the number of "exceptional vertices" w.r.t. to a closest convex coloring. The
problem was proved to be NP-hard even for colored string.
  In this paper we continue the work of [19], and present a 2-approximation
algorithm of convex recoloring of strings whose running time O(cn), where c is
the number of colors and n is the size of the input, and an O(cn^2)-time
3-approximation algorithm for convex recoloring of trees.
