In Vertex Coloring Problems, one is required to assign a color to each vertex of an undirected graph in such a way that adjacent vertices receive different colors, and the objective is to minimize the cost of the used colors. In this work we solve four different coloring problems formulated as Maximum Weight Stable Set Problems on an associated graph. We exploit the transformation proposed by Cornaz and Jost (2008), where given a graph G, an auxiliary graph Gˆ is constructed, such that the family of all stable sets of Gˆ is in one-to-one correspondence with the family of all feasible colorings of G. The transformation in Cornaz and Jost (2008) was originally proposed for the classical Vertex Coloring and the Max-Coloring problems; we extend it to the Equitable Coloring Problem and the Bin Packing Problem with Conflicts. We discuss the relation between the Maximum Weight Stable formulation and a polynomial-size formulation for the VCP, proposed by Campêlo et al. (2008) and called the Representative formulation. We report extensive computational experiments on benchmark instances of the four problems, and compare the solution method with the state-of-the-art algorithms. By exploiting the proposed method, we largely outperform the state-of-the-art algorithm for the Max-coloring Problem, and we are able to solve, for the first time to proven optimality, 14 Max-coloring and 2 Equitable Coloring instances.

Cornaz, D., Furini, F., Malaguti, E. (2017). Solving vertex coloring problems as maximum weight stable set problems. DISCRETE APPLIED MATHEMATICS, 217, 151-162 [10.1016/j.dam.2016.09.018].

### Solving vertex coloring problems as maximum weight stable set problems

#### Abstract

In Vertex Coloring Problems, one is required to assign a color to each vertex of an undirected graph in such a way that adjacent vertices receive different colors, and the objective is to minimize the cost of the used colors. In this work we solve four different coloring problems formulated as Maximum Weight Stable Set Problems on an associated graph. We exploit the transformation proposed by Cornaz and Jost (2008), where given a graph G, an auxiliary graph Gˆ is constructed, such that the family of all stable sets of Gˆ is in one-to-one correspondence with the family of all feasible colorings of G. The transformation in Cornaz and Jost (2008) was originally proposed for the classical Vertex Coloring and the Max-Coloring problems; we extend it to the Equitable Coloring Problem and the Bin Packing Problem with Conflicts. We discuss the relation between the Maximum Weight Stable formulation and a polynomial-size formulation for the VCP, proposed by Campêlo et al. (2008) and called the Representative formulation. We report extensive computational experiments on benchmark instances of the four problems, and compare the solution method with the state-of-the-art algorithms. By exploiting the proposed method, we largely outperform the state-of-the-art algorithm for the Max-coloring Problem, and we are able to solve, for the first time to proven optimality, 14 Max-coloring and 2 Equitable Coloring instances.
##### Scheda breve Scheda completa Scheda completa (DC)
2017
Cornaz, D., Furini, F., Malaguti, E. (2017). Solving vertex coloring problems as maximum weight stable set problems. DISCRETE APPLIED MATHEMATICS, 217, 151-162 [10.1016/j.dam.2016.09.018].
Cornaz, Denis; Furini, Fabio; Malaguti, Enrico
File in questo prodotto:
Eventuali allegati, non sono esposti

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/11585/585007`
##### Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

• ND
• 20
• 16