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.
展开▼
