Convex recoloring of paths

Let (T,C)(T,C) be a pair consisting of a tree TT and a coloring CC of its vertices. We say that CC is a convex coloring   if, for each color cc, the vertices in TT with color cc induce a subtree of TT. The convex recoloring problem   (of trees) is defined as follows. Given a pair (T,C)(T,C), find a recoloring of a minimum number of vertices of TT such that the resulting coloring is convex. This problem, known to be NP-hard, was motivated by problems on phylogenetic trees.We investigate here the convex recoloring problem on paths, denoted here as CRP. The main result concerns an approximation algorithm for a special case of CRP, denoted here as 22-CRP, restricted to paths in which the number of vertices of each color is at most  22, a problem known to be NP-hard. The best approximation result for CRP was obtained by Moran and Snir in 2007, who showed a 22-approximation algorithm. We show in this paper a 3/23/2-approximation algorithm for 22-CRP and show that its ratio analysis is tight.We also present an integer programming formulation for CRP and discuss some computational results obtained by exploring this formulation.