Convex recoloring of paths.

Abstract: Let be a pair consisting of a tree and a coloring of its vertices. We say that is a convex coloring if, for each color , the vertices in with color induce a subtree of . The convex recoloring problem (of trees) is defined as follows. Given a pair , find a recoloring of a minimum number of vertices of 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 -CRP, restricted to paths in which the number of vertices of each color is at most , a problem known to be NP-hard. The best approximation result for CRP was obtained by Moran and Snir in 2007, who showed a -approximation algorithm. We show in this paper a -approximation algorithm for -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. [Copyright &y& Elsevier]