Convex recoloring of paths

Let (T, C) be a pair consisting of a tree T and a coloring C of its vertices. We say that C is a convex coloring if, for each color c, the vertices in T with color c induce a subtree of T. The convex recoloring problem (of trees) is defined as follows. Given a pair (T, C), find a recoloring of a minimum number of vertices of T 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 2-CRP, restricted to paths in which the number of vertices of each color is at most 2, a problem known to be NP-hard. The best approximation result for CRP was obtained by Moran and Snir in 2007, who showed a 2-approximation algorithm. We show in this paper a 3/2-approximation algorithm for 2-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. (C) 2013 Elsevier B.V. All rights reserved.