Counting independent sets using the Bethe approximation

DOI10.1137/090767145MaRDI QIDQ3094955zbMATH OpenOpenAlexFDO

Authors Venkat Chandrasekaran, Misha Chertkov, David Gamarnik, Devavrat Shah, Jinwoo Shin

Publication date 27 October 2011

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/090767145

zbMATH Keywords

belief propagationBethe free energyindependent setloop series

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Recommendations

• On Counting Independent Sets in Sparse Graphs
• Counting independent sets up to the tree threshold
• Harnessing the Bethe free energy

Cited in

(6)

• Limits of discrete distributions and Gibbs measures on random graphs
• Convergence of MCMC and loopy BP in the tree uniqueness region for the hard-core model
• Spectral independence in high-dimensional expanders and applications to the hardcore model
• Diagonal stationary points of the Bethe functional
• Convergence and Correctness of Max-Product Belief Propagation for Linear Programming
• Gauges, loops, and polynomials for partition functions of graphical models

This page was built for publication: Counting independent sets using the Bethe approximation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3094955)