On counting independent sets in sparse graphs

Abstract:

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

This report is available in the following formats:

• PDF file
• Gzipped PDF file
• PostScript file
• Gzipped PostScript file
• PostScript file with Type 1 fonts
• Gzipped PostScript file with Type 1 fonts
• LaTeX DVI file
• Gzipped LaTeX DVI file