On counting independent sets in sparse graphs

Martin Dyer, Alan Frieze and Mark Jerrum


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:

Previous | Index | Next