×

Maximum-weight stable sets and safe lower bounds for graph coloring. (English) Zbl 1267.90005

Summary: The best method known for determining lower bounds on the vertex coloring number of a graph is the linear-programming column-generation technique, where variables correspond to stable sets, first employed by A. Mehrotra and M. A. Trick [INFORMS J. Comput. 8, No. 4, 344–354 (1996; Zbl 0884.90144)]. We present an implementation of the method that provides numerically-safe results, independent of the floating-point accuracy of linear-programming software. Our work includes an improved branch-and-bound algorithm for maximum-weight stable sets and a parallel branch-and-price framework for graph coloring. Computational results are presented on a collection of standard test instances, including the unsolved challenge problems created by David S. Johnson in 1989.

MSC:

90-04 Software, source code, etc. for problems pertaining to operations research and mathematical programming
90-08 Computational methods for problems pertaining to operations research and mathematical programming
90C27 Combinatorial optimization
90C35 Programming involving graphs or networks

Citations:

Zbl 0884.90144
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Andrade, D.V., Resende, M.G.C., Werneck, R.F.: Fast local search for the maximum independent set problem. In: Proceedings of workshop on experimental algorithms, pp. 220–234 (2008)
[2] Applegate D.L., Cook W., Dash S., Espinoza D.G.: Exact solutions to linear programming problems. Oper. Res. Lett. 35(6), 693–699 (2007) · Zbl 1177.90282 · doi:10.1016/j.orl.2006.12.010
[3] Babel L.: A fast algorithm for the maximum weight clique problem. Computing 52, 31–38 (1994) · Zbl 0791.68127 · doi:10.1007/BF02243394
[4] Balas E., Xue J.: Minimum weighted coloring of triangulated graphs with application to maximum weight vertex packing and clique finding in arbitrary graphs. SIAM J. Comput. 20(2), 209–221 (1991) · Zbl 0722.68086 · doi:10.1137/0220012
[5] Balas E., Yu C.: Finding a maximum clique in an arbitrary graph. SIAM J. Comput. 15(4), 1054–1068 (1986) · Zbl 0604.05024 · doi:10.1137/0215075
[6] Balas, E., Niehaus, W.: A max-flow based procedure for finding heavy cliques in vertex-weighted graphs. Tech. Rep. MSRR No. 612, GSIA, Carnegie-Mellon University (1995)
[7] Brélaz D.: New methods to color the vertices of a graph. Commun. ACM 22(4), 251–256 (1979) · Zbl 0394.05022 · doi:10.1145/359094.359101
[8] Busygin S.: A new trust region technique for the maximum weight clique problem. Discret. Appl. Math. 154, 2080–2096 (2006) · Zbl 1111.90020 · doi:10.1016/j.dam.2005.04.010
[9] Leighton F.T.: A graph coloring problem for large scheduling problems. J. Res. Natl. Bureau Stand. 84, 489–505 (1979) · Zbl 0437.68021 · doi:10.6028/jres.084.024
[10] Gualandi S., Malucelli F.: Exact solution of graph coloring problems via constraint programming and column generation. INFORMS J. Comput. 24(1), 81–100 (2012) · Zbl 1237.05075 · doi:10.1287/ijoc.1100.0436
[11] Hansen P., Labbé M., Schindl D.: Set covering and packing formulations of graph coloring: Algorithms and first polyhedral results. Discret. Optim. 6(2), 135–147 (2009) · Zbl 1279.90115 · doi:10.1016/j.disopt.2008.10.004
[12] Held S., Sewell, E.C., Cook, W.: Exact colors project webpage (2010). http://code.google.com/p/exactcolors/
[13] Lund C., Yannakakis M.: On the hardness of approximating minimization problems. J. ACM 41(5), 960–981 (1994) · Zbl 0814.68064 · doi:10.1145/185675.306789
[14] Malaguti E., Monaci M., Toth P.: An exact approach for the vertex coloring problem. Discret. Optim. 8(2), 174–190 (2011) · Zbl 1244.05092 · doi:10.1016/j.disopt.2010.07.005
[15] Malaguti E., Toth P.: A survey on vertex coloring problems. Int. Trans. Oper. Res. 17, 1–34 (2010) · Zbl 1223.05079 · doi:10.1111/j.1475-3995.2009.00696.x
[16] Mehrotra A., Trick M.A.: A column generation approach for graph coloring. INFORMS J. Comput. 8(4), 344–354 (1996) · Zbl 0884.90144 · doi:10.1287/ijoc.8.4.344
[17] Mittelmann H.: Benchmarks for optimization software (2011). http://plato.asu.edu/bench.html
[18] Mycielski J.: Sur le coloriage des graphes. Colloq. Math. 3, 161–162 (1955) · Zbl 0064.17805
[19] Méndez-Díaz I., Zabala P.: A branch-and-cut algorithm for graph coloring. Discret. Appl. Math. 154(5), 826–847 (2006) · Zbl 1120.90034 · doi:10.1016/j.dam.2005.05.022
[20] Méndez-Díaz I., Zabala P.: A cutting plane algorithm for graph coloring. Discret. Appl. Math. 156(2), 159–179 (2008) · Zbl 1163.90012 · doi:10.1016/j.dam.2006.07.010
[21] Porumbel D.C., Hao J.K., Kuntz P.: An evolutionary approach with diversity guarantee and well-informed grouping recombination for graph coloring. Comput. Oper. Res. 37(10), 1822–1832 (2010) · Zbl 1188.90269 · doi:10.1016/j.cor.2010.01.015
[22] Sewell E.C.: A branch and bound algorithm for the stability number of a sparse graph. INFORMS J. Comput. 10(4), 438–447 (1998) · doi:10.1287/ijoc.10.4.438
[23] Steffy, D.E.: Topics in exact precision mathematical programming. Ph.D. thesis, Georgia Institute of Technology (2011)
[24] Titiloye O., Crispin, A.: Graph coloring with a distributed hybrid quantum annealing algorithm. In: Proceedings of the 5th KES international conference on agent and multi-agent systems: technologies and applications, KES-AMSTA’11, Springer, Berlin, pp. 553–562 (2011)
[25] Titiloye O., Crispin A.: Quantum annealing of the graph coloring problem. Discret. Optim. 8(2), 376–384 (2011) · Zbl 1244.05097 · doi:10.1016/j.disopt.2010.12.001
[26] Trick M.: DIMACS graph coloring instances (2002). http://mat.gsia.cmu.edu/COLOR02/
[27] Warren, J., Hicks, I.: Combinatorial branch-and-bound for the maximum weight independent set problem. Technical report, Texas A&M University (2006)
[28] Wu Q., Hao J.K.: Coloring large graphs based on independent set extraction. Comput. Oper. Res. 39(2), 283–290 (2012) · Zbl 1250.05007 · doi:10.1016/j.cor.2011.04.002
[29] Zuckerman D.: Linear degree extractors and the inapproximability of max clique and chromatic number. Theory Comput. 3(1), 103–128 (2007) · Zbl 1213.68322 · doi:10.4086/toc.2007.v003a006
[30] P.R.J.: A new algorithm for the maximum-weight clique problem. Electron. Notes Discret. Math. 3, 153–156 (1999) · doi:10.1016/S1571-0653(05)80045-9
[31] Östergård, P.R.J., Niskanen, S.: Cliquer home page (2010). http://users.tkk.fi/pat/cliquer.html
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.