What algorithms/mathematical techniques are available to exactly/approximately count number of independent sets?
Is/Are there a good reference/good references on this topic?
I am interested in regular graphs.
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this communityWhat algorithms/mathematical techniques are available to exactly/approximately count number of independent sets?
Is/Are there a good reference/good references on this topic?
I am interested in regular graphs.
The problem can be restated as a #2SAT. See
http://en.wikipedia.org/wiki/2-satisfiability
under the "Counting the number of satisfying assignments" section for some references to the currently best exact counting algorithms.
For approximate counting, the following paper (also in APPROX-RANDOM 2011)
http://arxiv.org/abs/1105.5131
describes the state of the art.
As Anthony Labarre refers to in a comment above, there was a recent and unexpected breakthrough by Yufei Zhao showing a tight upper bound on the number of independent sets in an $n$-vertex $d$-regular graph. His proof used a very clever bijection. The extremal example, conjectured by Alon and Kahn and dating back to 1991, is simply a disjoint union of many copies of a $d$-regular complete bipartite graph.
This area of research draws on many mathematical and algorithmic methods, and is an area of interest not only to theoretical computer scientists, but also to number theorists, probabilists, combinatorialists, statistical physicists, and more. These two recent papers might give you a good start, though there is a rich collection of deep and interesting papers on the topic going back decades.
To supplement the answer from @RJK, as of yesterday, there is a new "state of the art."
Sly and Sun show
Theorem 1. For $d \ge 3$ and $\lambda > \lambda_c(d) = \frac{(d−1)^{d-1}}{(d-2)^d}$, unless NP = RP there exists no FPRAS for the partition function of the hard-core model with fugacity $\lambda$ on $d$-regular graphs.
For $\lambda < \lambda_c(d)$, it is already known that an FPRAS exists. Sly and Sun site those papers.
It is an open problem what happens when $\lambda = \lambda_c(d)$.