Faster Exponential-time Algorithms for Approximately Counting Independent Sets

Leslie Ann Goldberg, John Lapinskas, David Richerby

Counting the independent sets of a graph is a classical #P-complete problem, even in the bipartite case. We give an exponential-time approximation scheme for this problem which is…