Counting Solution Clusters Using Belief Propagation

We show that an important and hard-to-compute solutionspace feature of a Constraint Satisfaction Problem (CSP), namely the number of clusters of solutions, can be accurately estimated by a technique very similar counting the number of solutions. This cluster counting approach can be naturally written in terms of a factor graph, and using a variant of the Belief Propagation inference framework, we can accurately approximate cluster counts in random CSP problems. We illustrate the algorithm on random graph coloring instances of sizes up to 100,000 vertices. Moreover, we supply a methodology to calculate number of clusters exactly using advanced techniques from knowledge compilation domain, which scale up to several hundred variables.