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, the vertices in T with the same color induces 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 is known to be NP-hard [Shlomo Moran and Sagi Snir. Convex recolorings of strings and trees: definitions, hardness results and algorithms. J. Comput. System Sci., 74(5):850–869, 2008]. It was motivated by problems on phylogenetic trees [Shlomo Moran and Sagi Snir. Convex recolorings of strings and trees: definitions, hardness results and algorithms. J. Comput. System Sci., 74(5):850–869, 2008]. estigate here the convex recoloring problem on paths, denoted here CRP. We present an integer programming formulation for CRP and show some computational results obtained by exploring this formulation. We also present some preliminary results of a heuristic that is based on this formulation. Furthermore, we investigate a special case of CRP, denoted here 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 [Iyad Kanj and Dieter Kratsch. Convex recoloring revisited: Complexity and exact algorithms. In Algorithms and data structures, volume 5609 of Lect. Notes in Comput. Sci., pages 388–397. Springer, Berlin, 2009]. The best approximation result for CRP was obtained by Moran and Snir [Shlomo Moran and Sagi Snir. Efficient approximation of convex recolorings. J. Comput. System Sci., 73(7):1078–1089, 2007], who showed a 2-approximation algorithm. We show in this paper a 3/2-approximation algorithm for 2-CRP.