DIMACS Graphs: Benchmark Instances and Best Upper Bounds


Graph Coloring Instances with Difficult Upper Bounds

Notice: Given the continually growing number of coloring algorithms, the initial library was becoming too large (with quite dilluted information and cumbersome to read). As such, the result tables are now split, using a classification already proposed in certain papers:
  (i) local search algorithms (no populations, no hybridisations, no independent set isolation) and
 (ii) population-based algorithms, complex hybrid EAs, etc.
Personally, I don't consider that the value or the interest in these algorithms could ever be ranked according to the figures below. Besides the fact that the experimental conditions are very different, certain papers employ general meta-heuristic ideas, while others algorithms use very specific graph coloring techniques (e.g. isolating independent sets).

Local search algorithms
Graph best K /$ \chi$ References
dsjc250.5 28/? [2,3,7,15,18]
dsjc500.1 12/? [1,2,15,18]
dsjc500.5 48/? [1,15,18]
dsjc500.9 126/? [1,15,18]
dsjc1000.1 20/? [1,14,15,18]
dsjc1000.5 85/? [18]
dsjc1000.9 223/? [18]
Graph best K /$ \chi$ References
r250.5 66/65 [1]
r1000.1c 98/? [1,18]
r1000.5 234/234 [13]
dsjr500.1c 84/84 [17]
dsjr500.5 122/122 [13]
le450_25c 25/25 [1,18]
le450.25d 25/25 [1,18]
Graph best K /$ \chi$ References
flat300_28_0 28/28 [1,15,18]
flat1000_50_0 50/50 [1,15]
flat1000_60_0 60/60 [1,15]
flat1000_76_0 85/76 [18]
latin_square 99/? [2]
C2000.5 /? -
C4000.5 /? -

Hybrid and population-based methods
Graph best K /$ \chi$ References
dsjc250.5 28/? [6,7,12,14,18,19,20,22]
dsjc500.1 12/? [7,11,12,14,19,20,22]
dsjc500.5 48/? [6,7,11,14,19,20,22,23]
dsjc500.9 126/? [7,11,12,18,19,20,22,23]
dsjc1000.1 20/? [6,7,11,14,19,20,21,22,23]
dsjc1000.5 83/? [6,11,14,19,20,21,22,23]
dsjc1000.9 222/? [21,22,23]
Graph best K /$ \chi$ References
r250.5 65/65 [12,14,19,20,22,23]
r1000.1c 98/? [12,14 19,20,22 ]
r1000.5 234/234 [14]
dsjr500.1c 85/84 [12,14,19,20,22]
dsjr500.5 122/122 [14,19,20,22,23]
le450_25c 25/25 [12p. 353,14,19,20,22,23]
le450.25d 25/25 [12pp. 353,14, 19,20,22,23]
Graph best K /$ \chi$ References
flat300_28_0 29/28 [19,20]
flat1000_50_0 50/50 [12,7,14,19,20,21]
flat1000_60_0 60/60 [12,7,14,15,19,20,21]
flat1000_76_0 82/76 [14,19,20,21,22,23]
latin_square 97/? [23]
C2000.5 146/? [211]
C4000.5 260/? [211]
You have information about a new reference, see any error? Note it down here in a few seconds (or e-mail me):

Trivial Upper Bounds and Easy Dimacs Instances: {flat300_26,26}, {le450_15c,15}, {le450_15d,15}, {dsjc125.1,5}, {dsjc125.9,44}, {dsjc250.1,8}, {dsjc250.9,72}, {school1,14}, {school1_nsh,14} {dsjc125.5,17}, {le450_5a,5}, {le450_5b,5}, {le450_5c,5}, {le450_5d,5}, {le450_15a,15}, {le450_15b,15}, {le450_25a,25}, {le450_25b,25}, {r125.1,5}, {r125.1c,46}, {r125.5, 36}, {r250.1,8}, {r250.1c,64}, {r1000.1,20}, {dsjr500.1,12}. Legal colorings for the above instances (denoted in the form {G,K*}, where K* is the best upper bound) can be easily reached by many families of heuristics (perhaps only the first three instances might be somehow more difficult). Except for the first 10 graphs, all other upper bounds can be found in the 1996 paper of C. Morgenstern [12,p. 357]:

Graph Descriptions

All listed graphs are from the Dimacs benchmark [9], and, more exactly, they belong to the following families:

Bibliography

1. I. Blöchliger and N. Zufferey. A graph coloring heuristic using partial solutions and a reactive tabu scheme. Computers and Operations Research, 35(3):960-975, 2008

2. M. Chiarandini and T Stutzle. An application of iterated local search to graph coloring, 2002.

3. I. Devarenne, Mabed H., and A. Caminada. Intelligent neighborhood exploration in local search heuristics. In ICTAI '06: Proceedings of the 18th IEEE International Conference on Tools with Artificial Intelligence, pages 144-150, Washington, DC, USA, 2006. IEEE Computer Society.

4. C. Fleurent and J.A. Ferland. Object-oriented implementation of heuristic search methods for graph coloring, maximum clique, and satisfiability. In D.S. Johnson and M.A. Trick, editors, Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, 1996, volume 26 of DIMACS series in Discrete Mathematics and Theoretical Computer Science, pages 619--652. American Mathematical Society.

5. D.A. Fotakis, S.D. Likothanassis, and S.K. Stefanakos. An Evolutionary Annealing Approach to Graph Coloring. Applications of Evolutionary Computing. EvoWorkshops2001: EvoCOP, EvoFlight, EvoIASP, EvoLearn, and EvoSTIM. Proceedings, 2037:120-129, 2001.

6. P. Galinier and J.K. Hao. Hybrid Evolutionary Algorithms for Graph Coloring. Journal of Combinatorial Optimization, 3(4):379-397, 1999.

7. P. Galinier, A. Hertz, and N. Zufferey. An Adaptive Memory Algorithm for the K-colouring Problem. Discrete Applied Mathematics, 156(2):267–279, 2008.

8. D.S. Johnson, C.R. Aragon, L.A. McGeoch, and C. Schevon. Optimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning. Operations Research, 39(3):378-406, 1991.

9. D.S. Johnson and M. Trick. Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge. American Mathematical Society, 1996.

10. F.T. Leighton. A graph coloring algorithm for large scheduling problems. Journal of Research of the National Bureau of Standards, 84(6):489-503, 1979.

11. R. Dorne and J.K. Hao. A new genetic local search algorithm for graph coloring. In A. E. Eiben, T. Back, M. Schoenauer, and H.P. Schwefel, editors, PPSN, volume 1498 of LNCS, pages 745–754, 1998.

12. C. Morgenstern. Distributed coloration neighborhood search. In D.S. Johnson and M.A. Trick, editors, Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, volume 26 of DIMACS series in Discrete Mathematics and Theoretical Computer Science, pages 335--358. American Mathematical Society, 1996. Important: Some graphs are found under different names (i.e. G500,0.1 instead of dsjc500.1, see page 348); the table at page 357 does not summarise all the results from the whole paper.

13. S. Prestwich. Coloration Neighbourhood Search With Forward Checking. Annals of Mathematics and Artificial Intelligence, 34(4):327-340, 2002.

14. E. Malaguti, M. Monaci, and P. Toth. A Metaheuristic Approach for the Vertex Coloring Problem. INFORMS Journal on Computing, 20(2):302, 2008.

15. A. Hertz, M. Plumettaz, and N. Zufferey. Variable Space Search for Graph Coloring. Discrete Applied Mathematics , 156(13): 2551-2560, 2008.

16. E.C. Sewell. An improved algorithm for exact graph coloring. In D.S. Johnson and M.A. Trick, editors, Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, volume 26 of DIMACS series in Discrete Mathematics and Theoretical Computer Science , pages 359--376. American Mathematical Society, 1996.

17. B. Benhamou and M.R. Saidi. Etude de la dominance dans les CSPs a contraintes de difference. Journees Francophones de Programmation par Contraintes, 2006, 63-70 [In French]

18. D. Porumbel, J.K. Hao and P Kuntz. A Search Space "Cartography" for Guiding Graph Coloring Heuristics. Computers & Operations Research , 37(4): 769-778, 2010.

19. Zhipeng Lü and Jin-Kao Hao, A Memetic Algorithm for Graph Coloring, European Journal of Operational Research, 203(1): 241-250, 2010.

20. D. Porumbel, J.K. Hao and P Kuntz. An Evolutionary Approach with Diversity Guarantee and Well-Informed Grouping Recombination for Graph Coloring, Computers & Operations Research, 37(10):1822-1832, 2010.

21. Qinghua Wu, Jin-Kao Hao. Coloring large graphs based on independent set extraction Computers and Operations Research, 39: 283-290, 2012

22. Olawale Titiloye, Alan Crispin. Quantum annealing of the graph coloring problem, Discrete Optimization, 8: 376-384, 2011

23. Olawale Titiloye, Alan Crispin. Graph Coloring with a Distributed Hybrid Quantum Annealing Algorithm. In J. O'Shea, N. Nguyen, K. Crockett, R. Howlett, L. Jain (eds.), Agent and Multi-Agent Systems: Technologies and Applications, vol. 6682 of Lecture Notes in Computer Science, pp. 553-562. 2011, Springer Berlin / Heidelberg. ISBN 978-3-642-21999-3.

Footnotes

1
These large graphs are probably best colored by removing independent sets and applying algorithms on the residual graph (see also 4).

Acknowledgements

This library should be up-to-date, as of August 2011. The first version was created in 2008 by Daniel Porumbel in his PhD project with Jin Kao Hao and Pascale Kuntz. Detailed corrections and verifications were performed by Jean Philippe Hamiez, whose help is acknowledged. Most graph files are obtained from M. Trick's page; however, some files were also obtained via private correspondence. The first html version was produced by LaTeX2HTML translator. However, you might also want to check the project Graph Coloring Benchmarks, that is constructed on wiki collaborative work where anybody could contribute.


Back home Total visits: