Conflict Optimization for Binary CSP Applied to Minimum Partition into Plane Subgraphs and Graph Coloring
Authors: 
Loïc Crombez, 
Guilherme D. Da Fonseca, Florian Fontan, Yan Gerard, Aldo Gonzalez-Lorenzo, Pascal Lafourcade, Luc Libralesso, Benjamin Momège, Jack Spalding-Jamieson, Brandon Zhang, Da Wei ZhengAuthors Info & Claims
Article No.: 1.2, Pages 1 - 13
Abstract
CG:SHOP is an annual geometric optimization challenge and the 2022 edition proposed the problem of coloring a certain geometric graph defined by line segments. Surprisingly, the top three teams used the same technique, called conflict optimization. This technique has been introduced in the 2021 edition of the challenge, to solve a coordinated motion planning problem. In this article, we present the technique in the more general framework of binary constraint satisfaction problems (binary CSP). Then, the top three teams describe their different implementations of the same underlying strategy. We evaluate the performance of those implementations to vertex color not only geometric graphs, but also other types of graphs.
References
[1]
Ivo Blöchliger and Nicolas Zufferey. 2008. A graph coloring heuristic using partial solutions and a reactive tabu scheme. Computers & Operations Research 35, 3 (2008), 960–975. DOI:
[2]
Daniel Brélaz. 1979. New methods to color the vertices of a graph. Communications of the ACM 22, 4 (1979), 251–256. DOI:
[3]
Loïc Crombez, Guilherme Dias da Fonseca, Yan Gerard, and Aldo Gonzalez-Lorenzo. 2022. Shadoks approach to minimum partition into plane subgraphs (CG challenge). In Proceedings of the 38th International Symposium on Computational Geometry.Xavier Goaoc and Michael Kerber (Eds.), Vol. 224, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 71:1–71:8. DOI:
[4]
Loïc Crombez, Guilherme Dias da Fonseca, Yan Gerard, Aldo Gonzalez-Lorenzo, Pascal Lafourcade, and Luc Libralesso. 2022. Shadoks approach to low-makespan coordinated motion planning. ACM Journal of Experimental Algorithmics 27, Article No. 3.2 (2022), 1–17.
[5]
David Eppstein. 2002. Small maximal independent sets and faster exact graph coloring. J. Graph Algorithms Appl 7, 2 (2002), 131–140.
[6]
Sándor P. Fekete, Phillip Keldenich, Dominik Krupke, and Stefan Schirra. 2023. Minimum partition into plane subgraphs: The CG: SHOP challenge 2022. Journal of Experimental Algorithms 28 (2023).
[7]
Florian Fontan, Pascal Lafourcade, Luc Libralesso, and Benjamin Momège. 2022. Local search with weighting schemes for the CG: SHOP 2022 competition (CG challenge). In Proceedings of the 38th International Symposium on Computational Geometry.Xavier Goaoc and Michael Kerber (Eds.), Vol. 224, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 73:1–73:6. DOI:
[8]
Fabio Furini, Virginie Gabrel, and Ian-Christopher Ternier. 2017. An improved DSATUR-based branch-and-bound algorithm for the vertex coloring problem. Networks 69, 1 (2017), 124–141. DOI:
[9]
Fabio Furini and Enrico Malaguti. 2012. Exact weighted vertex coloring via branch-and-price. Discrete Optimization 9, 2 (2012), 130–136. DOI:
[10]
Philippe Galinier and Jin-Kao Hao. 1999. Hybrid evolutionary algorithms for graph coloring. Journal of Combinatorial Optimization 3, 4 (1999), 379–397. DOI:
[11]
Olivier Goudet, Cyril Grelier, and Jin-Kao Hao. 2022. A deep learning guided memetic framework for graph coloring problems. arXiv:2109.05948.
[12]
Stefano Gualandi and Federico Malucelli. 2012. Exact solution of graph coloring problems via constraint programming and column generation. INFORMS Journal on Computing 24, 1 (2012), 81–100. DOI:
[13]
Alain Hertz and Dominique de Werra. 1987. Using tabu search techniques for graph coloring. Computing 39, 4 (1987), 345–351. DOI:
[14]
Tommy R. Jensen and Bjarne Toft. 2011. Graph Coloring Problems. John Wiley & Sons.
[15]
David S. Johnson and Michael A. Trick. 1996. Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, October 11–13, 1993. Vol. 26. American Mathematical Society.
[16]
Frank Thomson Leighton. 1979. A graph coloring algorithm for large scheduling problems. Journal of Research of the National Bureau of Standards 84, 6 (1979), 489. DOI:
[17]
R. M. R. Lewis. 2015. A Guide to Graph Colouring: Algorithms and Applications (1st. ed.). Springer Publishing Company, Incorporated.
[18]
C. Lucet, F. Mendes, and A. Moukrim. 2006. An exact method for graph coloring. Computers and Operations Research 33, 8 (2006), 2189–2207. DOI:
[19]
David W. Matula, George Marble, and Joel D. Isaacson. 1972. Graph coloring algorithms. In Proceedings of the Graph Theory and Computing.Ronald C. Read (Ed.), Academic Press, 109–122. DOI:
[20]
Anuj Mehrotra and Michael A. Trick. 1996. A column generation approach for graph coloring. INFORMS Journal on Computing 8, 4 (1996), 344–354. DOI:
[21]
Steven Minton, Mark D. Johnston, Andrew B. Philips, and Philip Laird. 1992. Minimizing conflicts: A heuristic repair method for constraint satisfaction and scheduling problems. Artificial Intelligence 58, 1–3 (1992), 161–205. DOI:
[22]
Laurent Moalic and Alexandre Gondran. 2018. Variations on memetic algorithms for graph coloring problems. Journal of Heuristics 24, 1 (2018), 1–24.
[23]
Isabel Méndez-Díaz and Paula Zabala. 2006. A branch-and-cut algorithm for graph coloring. Discrete Applied Mathematics 154, 5 (2006), 826–847. DOI:
[24]
Pablo San Segundo. 2012. A new DSATUR-based algorithm for exact vertex coloring. Computers and Operations Research 39, 7 (2012), 1724–1733. DOI:
[25]
André Schidler. 2022. SAT-based local search for plane subgraph partitions (CG challenge). In Xavier Goaoc and Michael Kerber (Eds.), Vol. 224, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 74:1–74:8. DOI:
[26]
Jack Spalding-Jamieson, Brandon Zhang, and Da Wei Zheng. 2022. Conflict-based local search for minimum partition into plane subgraphs (CG challenge). In Proceedings of the 38th International Symposium on Computational Geometry.Xavier Goaoc and Michael Kerber (Eds.), Vol. 224, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 72:1–72:6. DOI:
[27]
Olawale Titiloye and Alan Crispin. 2011. Quantum annealing of the graph coloring problem. Discrete Optimization 8, 2 (2011), 376–384. DOI:
[28]
Olawale Titiloye and Alan Crispin. 2012. Parameter tuning patterns for random graph coloring with quantum annealing. PloS One 7, 11 (2012). DOI:
[29]
Edward P. K. Tsang. 1993. Foundations of Constraint Satisfaction. Computation in Cognitive Science, Academic Press. https://dblp.org/rec/books/daglib/0076790.bib.
[30]
D. J. A. Welsh and M. B. Powell. 1967. An upper bound for the chromatic number of a graph and its application to timetabling problems. The Computer Journal 10, 1(1967), 85–86.
Index Terms
- Conflict Optimization for Binary CSP Applied to Minimum Partition into Plane Subgraphs and Graph Coloring
Recommendations
Planar Graph Coloring with Forbidden Subgraphs: Why Trees and Paths Are Dangerous
SWAT '02: Proceedings of the 8th Scandinavian Workshop on Algorithm TheoryWe consider the problem of coloring a planar graph with the minimum number of colors such that each color class avoids one or more forbidden graphs as subgraphs. We perform a detailed study of the computational complexity of this problem.We present a ...
List-coloring the square of a subcubic graph
The square G2 of a graph G is the graph with the same vertex set G and with two vertices adjacent if their distance in G is at most 2. Thomassen showed that every planar graph G with maximum degree Δ(G) = 3 satisfies χ(G2) ≤ 7. Kostochka and Woodall ...
Minimum order of graphs with given coloring parameters
A complete k -coloring of a graph G = ( V , E ) is an assignment : V { 1 , , k } of colors to the vertices such that no two vertices of the same color are adjacent, and the union of any two color classes contains at least one edge. Three extensively ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 11 May 2023
Online AM: 27 March 2023
Accepted: 12 February 2023
Revised: 22 November 2022
Received: 22 November 2022
Published in JEA Volume 28
Author Tags
Qualifiers
- Research-article
Funding Sources
- French government research program “Investissements d’Avenir” through the IDEX-ISITE initiative 16-IDEX-0001
- French ANR PRC
- French ANR PRC
- ACTIVmap
- French government IDEX-ISITE initiative 16-IDEX-0001
- French ANR PRC grant MobiS5
- DECRYPT
- SEVERITAS
- French government IDEX-ISITE initiative 16-IDEX-0001
- French ANR PRC grant DECRYPT
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 226Total Downloads
- Downloads (Last 12 months)109
- Downloads (Last 6 weeks)9
Reflects downloads up to 16 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign inFull Access
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderFull Text
View this article in Full Text.
Full TextHTML Format
View this article in HTML Format.
HTML Format