Counting Solution Clusters in Graph Coloring Problems Using Belief Propagation
Lukas Kroc, Ashish Sabharwal, Bart Selman Known facts:
Solution space of random combinatorial problems fractures into clusters as constraint density (& hardness) increases The fastest solution technique relies on marginal probability estimates over clusters
One giant cluster Many small clusters

Poster ID:

M48

Cornell University

Our results:
An expression to count the number of clusters with high precision

Z ( -1 ) =

r y DomExt n



(- 1)

r #e ( y )

 

r f ( y )

No solutions

A message-passing scheme similar to BP that approximates Z(-1) well

Constraint density

= cluster of satisfying assignments = trap (almost satisfying)