Artículos de revistas
Polyhedral studies on the convex recoloring problem
Fecha
2013-11-05Registro en:
Electronic Notes in Discrete Mathematics, Amsterdam, v. 44, p. 233–238, nov. 2013
1571-0653
10.1016/j.endm.2013.10.036
Autor
Neto, Manoel Bezerra Campêlo
Lima, Karla Roberta Pereira Sampaio
Moura, Phablo Fernando Soares
Wakabayashi, Yoshiko
Institución
Resumen
A coloring of the vertices of a graph G is convex if, for each assigned color d, the vertices with color d induce a connected subgraph of G. We address the convex recoloring problem, defined as follows. Given a graph G and a coloring of its vertices, recolor a minimum number of vertices of G, so that the resulting coloring is convex. This problem is known to be NP-hard even when G is a path. We show an integer programming formulation for the weighted version of this problem on 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 discuss separation algorithms.