LOCo - Convex Recoloring Problem

Home / files / instances / CRP

Convex Recoloring Problem - Benchmark Instances and Solutions

by A. P. S. Dantas, C. C. de Souza and Z. Dias

Citing this page:

Use the BibTeX entry:

@Misc{crp-instances-page,  
 author = {Ana P. S. Dantas and Cid C. de Souza and Zanoni Dias},  
 title = {Convex Recoloring Problem - Benchmark Instances and Solutions},  
 year = {2018},  
 url = {https://www.loco.ic.unicamp.br/files/instances/convex-recoloring}  
}

Problem description

Let $G=(V,E)$ be a graph, with $V$ as the set of vertices and $E \subseteq V \times V$ as the set of edges. Let $\mathcal{C}$ be a set of colors and $C$ be a coloring function such that $C : V \rightarrow \mathcal{C}$. A color class is the set of all vertices that are colored with $c$, for $c \in \mathcal{C}$. A color class is said convex if it induces a connected subgraph. Given the graph $ G$ and a coloring of it, $(G,C)$ is dubbed a colored graph. A coloring $C’$ of a colored graph $(G,C)$ is a recoloring of $G$. Given a colored graph $(G,C)$ and a recoloring $C’$ of $G$, the Convex Recoloring Problem (CRP) seeks the minimum number of vertices that need to be recolored such the recoloring is convex, i.e, every color class is convex.

The pictures below show an example of an instance of the CRP. Figure (a) shows a colored graph. Figure (b) shows a suboptimal convex recoloring and Figure (c) shows an optimal convex recoloring. Note that recolored vertices in Figures (b) and (c) are circled by their original colors.

(a) An instance for the CRP

(b) Convex recoloring

Input Instances

There are 100 Erdos-Renyi connected random graphs for each $n \in \{10, 20, \dots, 100\}$ and $p \in \{0.1, 0.2, \dots,0.5\}$, with $n$ as the number of vertices of the graph and $p$ the probability of adding an edge. To create hard instances we use a proper coloring for each of these graphs, that is, no two neighbor vertices have the same color. We used the greedy algorithm introduced in Bondy and Murty [1]. Starting with such coloring, we apply a balancing procedure that moves vertices from the largest to the smallest color class, whilst maintaining the proper coloring property.

The instances are separeted in folders by number of vertices. Inside each folder there are 500 instances. Their name are in the format:

$n$_$p$_$id$.gcc

$n$: Number of vertices, with $n \in \{010, 020, \dots, 100\}$;
$p$: Edge probability, with $p \in \{010, 020, \dots, 050\}$;
$id$: Identication distinguishing instances of the number of vertices and probability, with $id \in \{000, 001, \dots, 099\}$.

Instance Files Format

Each instance file lists the edges of the graph and the initial coloring. The lines of the file are described below in order of appearance:

     1 line with the instance name
     1 line with number of vertices
     1 line with number of edges
     1 line with number of colors
     $m$ lines describing the edges, in the format: <$u$> <$v$>, with $u, v, \in V$
     $n$ lines describing the coloring, in the format: <$u$> <$c$>, with $u \in V$ and $c \in \mathcal{C}$

Download the instance files here.

Solutions

We present the solutions for Integer Linear Programming model by Campêlo et al.[2] and for the GRASP based algorithm by Dantas, de Souza e Dias [3].

Experiments’ Details

The model was coded in the programming language C++, compiled using g++ (version 5.4), with flag C++11, and solved by IBM’s CPLEX (version 12.8). We used a time limit of 30 minutes for the execution of the model.

The GRASP also was implemented using the programming language C++, with the compiler flags C++11 and -O3, and compiler g++ (version 5.4). We used $2n^2$ iterations and the R package Iterated Race Automatic Algorithm Configuration (irace) [4] to define the percentage to be considered in the random selection of the candidates.

All experiments were carried out on an Intel® Core™ i7 3.40GHz machine with 32GB of RAM running Ubuntu 18.04 LTS. For more details see the computational results in [3].

Solution Files Format

Each instance file has two solution files. The first is the solution from the Integer Linear Programming model, and is described bellow:

     1 line with: <instance name> <execution time> <gap> <number of recolored vertices>
     1 line with the number of vertices
     1 line with the number of colors
     $n$ lines describing the recoloring, in the format: <$u$> <$c$>, with $u \in V$ and $c \in \mathcal{C}$

Download the model’s solution files here.

The second solution file is from the GRASP, and is described bellow:

     1 line with: <instance name> <execution time> <seed> <total of iterations> <neighborhood> <number of recolored vertices>
     1 line with the number of vertices
     1 line with the number of colors
     $n$ lines describing the recoloring, in the format: <$u$> <$c$>, with $u \in V$ and $c \in \mathcal{C}$

Download the GRASP’s solution files here.

Acknowledgments

This work was supported by grants from Conselho Nacional de Desenvolvimento Científico e Tecnológico (304727/2014-8, 400487/2016-0, 425340/2016-3, and 140466/2018-5), Fundação de Amparo à Pesquisa do Estado de São Paulo (2013/08293-7, 2015/11937-9, 2017/12646-3, 2017/16246-0, and 2018/04760-3), Coordenação de Aperfeiçoamento do Pessoal do Ensino Superior and the CAPES/COFECUB program (831/15).

References

[1] Bondy, J. A. and U. S. R. Murty. Graph Theory, Graduate Texts in Mathematics 244, Springer, London, 2011, 1st edition.
[2] Campêlo, M. B., A. S. Freire, K. R. Lima, P. F. S. Moura and Y. Wakabayashi, The Convex Recoloring Problem: Polyhedra, Facets and Computational Experiments, Math. Program. 156 (2016), pp. 303–330.
[3] Dantas, A. P. S., C. C. de Souza and Z. Dias, A GRASP for the Convex Recoloring Problem in Graphs, submited (2018).
[4] López-Ibáñez, M., J. Dubois-Lacoste, L. Pérez Cáceres, T. Süttzle and M. Birattari, The irace package: Iterated racing for automatic algorithm configuration, Oper. Res. Perspect. 3 (2016), pp. 43–58.