Counting Solution Clusters in Graph Coloring Problems Using Belief Propagation

We show that an important and computationally challenging solution space feature of the graph coloring problem (COL), namely the number of clusters of solutions, can be accurately estimated by a technique very similar to one for counting the number of solutions. This cluster counting approach can be naturally written in terms of a new factor graph derived from the factor graph representing the COL instance. Using a variant of the Belief Propagation inference framework, we can efficiently approximate cluster counts in random COL problems over a large range of graph densities. We illustrate the algorithm on instances with up to 100, 000 vertices. Moreover, we supply a methodology for computing the number of clus- ters exactly using advanced techniques from the knowledge compilation literature. This methodology scales up to several hundred variables.

Authors

• Lukas Kroc Michael Chertkov
• Ashish Sabharwal
• Bart Selman

Keywords

No keywords are indexed for this paper.