The Convex Recoloring Problem: Polyhedra, Facets And Computational Experiments

A coloring of the vertices of a graph (Formula presented.) is convex if the vertices receiving a common color induce a connected subgraph of (Formula presented.). We address the convex recoloring problem: given a graph (Formula presented.) and a coloring of its vertices, recolor a minimum number of vertices of (Formula presented.), so that the resulting coloring is convex. This problem is known to be (Formula presented.)-hard even when (Formula presented.) is a path. We show an integer programming formulation for arbitrary graphs, and then specialize it for trees. We study the facial structure of the polytope defined as the convex hull of the integer points satisfying the restrictions of the proposed ILP formulation, present several classes of facet-defining inequalities and the corresponding separation algorithms. We also present a branch-and-cut algorithm that we have implemented for the special case of trees, and show the computational results obtained with a large number of instances. We consider instances which are real phylogenetic trees. The experiments show that this approach can be used to solve instances up to (Formula presented.) vertices in 2 h, comparing favorably to other approaches that have been proposed in the literature