Timezone: »

 
Poster
Counting Solution Clusters Using Belief Propagation
Lukas Kroc · Ashish Sabharwal · Bart Selman

Mon Dec 08 08:45 PM -- 12:00 AM (PST) @
in Posters »

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.

[ PDF] 

Author Information

Lukas Kroc (Cornell University)
Ashish Sabharwal (Cornell University)
Bart Selman (Cornell University)

More from the Same Authors