Clause Learning and New Bounds for Graph Coloring

Abstract : Graph coloring is a major component of numerous allocation and scheduling problems. We introduce a hybrid CP/SAT approach to graph coloring based on exploring Zykov's tree: for two non-neighbors, either they take a different color and there might as well be an edge between them, or they take the same color and we might as well merge them. Branching on whether two neighbors get the same color yields a symmetry-free tree with complete graphs as leaves, which correspond to colorings of the original graph. We introduce a new lower bound for this problem based on Mycielskian graphs; a method to produce a clausal explanation of this bound for use in a CDCL algorithm; and a branching heuristic emulating Brelaz on the Zykov tree. The combination of these techniques in both a branch-and-bound and in a bottom-up search outperforms Dsatur and other SAT-based approaches on standard benchmarks both for finding upper bounds and for proving lower bounds.
Document type :
Conference papers
Complete list of metadatas

Cited literature [26 references]  Display  Hide  Download

https://hal.laas.fr/hal-01873500
Contributor : Emmanuel Hebrard <>
Submitted on : Thursday, September 13, 2018 - 12:42:08 PM
Last modification on : Thursday, February 20, 2020 - 7:22:08 PM
Long-term archiving on: Friday, December 14, 2018 - 2:37:17 PM

File

paper.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01873500, version 1

Citation

Emmanuel Hébrard, George Katsirelos. Clause Learning and New Bounds for Graph Coloring. International Conference on Principles and Practice of Constraint Programming (CP 2018), Aug 2018, Lille, France. 17p. ⟨hal-01873500⟩

Share

Metrics

Record views

122

Files downloads

111