On Counting Independent Sets in Sparse Graphs

We prove two results concerning approximate counting of independent sets in graphs with constant maximum degree /spl Delta/. The first result implies that the Monte-Carlo Markov chain technique is likely to fail if /spl Delta//spl ges/6. The second shows that no fully polynomial randomized approximation scheme can exist for /spl Delta//spl ges/25, unless P=NP under randomized reductions.

Authors

• Martin E. Dyer
• Alan M. Frieze
• Mark Jerrum

Keywords

• Radio access networks
• Monte Carlo methods
• Mathematics
• Computer science
• Electronic switching systems
• Polynomials
• Bipartite graph
• Independent Set
• Set Of Graphs
• Sparse Graph
• Markov Chain
• Markov Chain Monte Carlo
• Maximum Degree
• Perfect Match
• Mixing Time
• Remainder Of This Section
• Polynomial-time Algorithm
• Random Graph
• Single Maximum
• Multiset
• Regular Graphs
• Class Of Graphs