Exact Algorithms for the Graph Coloring Problem
Keywords:Graph Theory, Graph Coloring, Exact Algorithms
The graph coloring problem is the problem of partitioning the vertices of a graph into the smallest possible set of independent
sets. Since it is a well-known NP-Hard problem, it is of great interest of the computer science finding results over exact algorithms that solve it. The main algorithms of this kind, though, are scattered through the literature. In this paper, we group and contextualize some of these algorithms, which are based in Dynamic Programming, Branch-and-Bound and Integer Linear Programming. The algorithms for the first group are based in the work of Lawler, which searches maximal independent sets on each subset of vertices of a graph as the base of his algorithm. In the second group, the algorithms are based in the work of Brelaz, which adapted the DSATUR procedure to an exact version, and in the work of Zykov, which introduced the definition of Zykov trees. The third group contains the algorithms based in the work of Mehrotra and Trick, which uses the Column Generation method.
LEWIS, R. A Guide to Graph Colouring: Algorithms and Applications. 1. ed. Berlin: Springer, 2016. v. 1.
GROTSCHEL, M.; LOVÀSZ, L.; SCHRIJVER, A. Polynomial algorithms for perfect graphs. In: BERGE, C.; CHVÀTAL, V. (Ed.). Topics on Perfect Graphs. 1.
ed. North-Holland, Holland: North-Holland Publishing Company, 1984, (North-Holland Mathematics Studies, v. 88). p. 325–356.
CORMEN, T. H. et al. Introduction to Algorithms. 3. ed. Massachusetts, USA: MIT Press, 2009. v. 1. I–XIX, 1–1292 p.
LAWLER, E. A note on the complexity of the chromatic number problem. Inform. Process. Lett., v. 5, n. 3, p. 66–67, 1976.
EPPSTEIN, D. Small maximal independent sets and faster exact graph coloring. J. Graph Algorithms Appl., v. 7, n. 2, p. 131–140, 2003.
BYSKOV, J. M. Chromatic number in time O(2.4023n) using maximal independent sets. BRICS Rep. Ser., v. 9, n. 45, p. 1–9, 2002.
BODLAENDER, H. L.; KRATSCH, D. An exact algorithm for graph coloring with polynomial memory. UU-CS, v. 2006, n. 15, p. 1–5, 2006.
WANG, C. C. An algorithm for the chromatic number of a graph. J. ACM, v. 21, n. 3, p. 385–391, 1974.
TSUKIYAMA, S. et al. A new algorithm for generating all the maximal independent sets. SIAM J. Comput., v. 6, n. 3, p. 505–517, 1977.
MOON, J.; MOSER, L. On cliques in graphs. Israel J. Math., v. 3, n. 1, p. 23–28, 1965.
MADSEN, B. A.; BYSKOV, J. M.; SKJERNAA, B. On the number of maximal bipartite subgraphs of a graph. BRICS Rep. Ser., v. 9, n. 17, p. 1–10, 2002.
LIMA, A. M. de. Algoritmos Exatos para o Problema da Coloração de Grafos. Dissertação (Mestrado) — Universidade Federal do Paraná, Parana, Brazil, 2017.
BEIGEL, R.; EPPSTEIN, D. 3-coloring in time O(1.3289n). J. Algorithm., v. 54, n. 2, p. 168 – 204, 2005.
BYSKOV, J. Enumerating maximal independent sets with applications to graph colouring. Oper. Res. Lett., v. 32, n. 6, p. 547–556, 2004.
BRÉLAZ, D. New methods to color the vertices of a graph. Commun, ACM, v. 22, n. 4, p. 251–256, 1979.
ZYKOV, A. On some properties of linear complexes. Mat. Sb. (N.S.), v. 24(66), n. 2, p. 418–419, 1962.
BROWN, J. R. Chromatic scheduling and the chromatic number problem. Manage. Sci., v. 19, n. 4-part-1, p. 456–463, 1972.
SEWELL, E. C. A branch and bound algorithm for the stability number of a sparse graph. INFORMS J. ON COMPUT., v. 10, n. 4, p. 438–447, 1998.
SEGUNDO, P. S. A new DSATUR-based algorithm for exact vertex coloring. Comput. Oper. Res., v. 39, n. 7, p. 1724–1733, 2012.
FURINI, F.; GABREL, V.; TERNIER, I.-C. An improved dsatur-based branch-and-bound algorithm for the vertex coloring problem. Networks, v. 69, n. 1, p. 124–141, 2017.
SEWELL, E. C. An improved algorithm for exact graph coloring. DIMACS ser. discrete math. theor. comput. sci., v. 26, n. 1, p. 359–373, 1996.
MATHEMATICS, C. for D.; SCIENCE,
T. C. DIMACS Implementation Challenges. 1994. Online; accessed 04 July 2018. Disponível em: <http://dimacs.rutgers.edu/archive/Challenges/>.
NETO, A. S. A.; GOMES, M. J. N. Problema e algoritmos de coloração em grafos - exatos e heurísticos. Rev. Sist. Comput., v. 4, n. 2, p. 201–115, 2014.
CORNEIL, D. G.; GRAHAM, B. An algorithm for determining the chromatic number of a graph. SIAM J. Comput., v. 2, n. 4, p. 311–318, 1973.
MCDIARMID, C. Determining the chromatic number of a graph. SIAM J. Comput., v. 8, n. 1, p. 1–14, 1979.
MEHROTRA, A.; TRICK, M. A. A column generation approach for graph coloring. INFORMS J. Comput., v. 8, n. 4, p. 344–354, 1995.
MATOUŠEK, J.; GÄRTNER. Understanding and using linear programming. 1. ed. Berlin, Germany: Springer, 2007. v. 1. (Universitext, v. 1).
DANTZIG, G. Linear programming and extensions. 1. ed. Princeton, NJ: Princeton Univ. Press, 1963. v. 1. (Rand Corporation Research Study, v. 1).
PAPADIMITRIOU, C. H.; STEIGLITZ, K. Combinatorial Optimization: Algorithms and Complexity. 1. ed. New Jersey, USA: Prentice-Hall, Inc., 1998. v. 1.
LUND, C.; YANNAKAKIS, M. On the hardness of approximating minimization problems. J. ACM, v. 41, n. 5, p. 960–981, 1994.
BARNHART, C. et al. Branch-and-price: Column generation for solving huge integer programs. Oper. Res., v. 46, n. 3, p. 316–329, 1998.
ANDRADE, C. E. d.; MIYAZAWA, F. K.; XAVIER, E. C. Um algoritmo exato para o Problema de Empacotamento Bidimensional em Faixas. Dissertação (Mestrado) — Instituto de Computação Universidade Estadual de Campinas, São Paulo, Brazil, 2006.
MALAGUTI, E.; MONACI, M.; TOTH, P. An exact approach for the vertex coloring problem. Discrete Optim., v. 8, n. 2, p. 174–190, 2011.
GUALANDI, S.; MALUCELLI, F. Exact solution of graph coloring problems via constraint programming and column generation. INFORMS J. Comput., v. 24, n. 1, p. 81–100, 2012.
DESAULNIERS, G.; DESROSIERS, J.; SOLOMON, M. Column Generation. 1. ed. Springer US: Springer US, 2006. v. 1. (GERAD 25th anniversary series, v. 1).