<p>For approximate counting, the following paper (also in APPROX-RANDOM 2011)</p>

<p><a href="http://arxiv.org/abs/1105.5131">http://arxiv.org/abs/1105.5131</a></p>

<p>describes the state of the art.</p>

<p>As Anthony Labarre refers to in a comment above, there was a recent and unexpected breakthrough by Yufei Zhao showing a <em>tight</em> 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.</p>

<p>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.</p>

CC BY-SA 3.0
2012-03-14T14:59:23.747Z
2012-03-14T14:59:23.747Z
RJK
<p>To supplement the answer from @RJK, as of yesterday, there is a new "state of the art."</p>

<p><a href="http://arxiv.org/abs/1203.2602" rel="noreferrer">Sly and Sun</a> show</p>

<blockquote>
  <p>Theorem 1. For $d \ge 3$ and $\lambda &gt; \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.</p>
</blockquote>

<p>For $\lambda &lt; \lambda_c(d)$, it is already known that an FPRAS exists. Sly and Sun site those papers.</p>

<p>It is an open problem what happens when $\lambda = \lambda_c(d)$.</p>

CC BY-SA 3.0
2012-03-14T19:03:00.887Z
Do you know if these results hold for graphs with specific structure such as strong, weak (etc) products whose underlying graph is dergee less than 3 and which has the value of lambda less than the above?
v s
CC BY-SA 3.0
2012-03-15T01:21:30.117Z
@v These graphs are regular?
Tyson Williams
CC BY-SA 3.0
2012-03-15T01:24:55.587Z
Yes. But does the results imply for all regular graphs, without caveat?? (I am thinking something analogous to this - we know it is NP hard to ML decode a linear code.. but it is very hard to show for specific non-trivial codes like RS codes and also it is known there are codes where ML decoding is easy) Of course it looks like the result here holds for all regular graphs.. but there are cases where symmetry of the graph may help as well and I don't see these graphs (in the paper) are assumed to have any symmetry at all!!
v s
CC BY-SA 3.0
2012-03-15T12:54:01.040Z
@v This result holds for all $d$-regular graphs. I don't know too much about coding theory.  Maybe you should ask a new question.
Tyson Williams
CC BY-SA 3.0
2012-03-14T17:13:25.747Z
2012-03-14T17:13:25.747Z
Tyson Williams
<p>The problem can be restated as a #2SAT. See </p>

<p><a href="http://en.wikipedia.org/wiki/2-satisfiability">http://en.wikipedia.org/wiki/2-satisfiability</a> </p>

<p>under the "Counting the number of satisfying assignments" section for some references to the currently best exact counting algorithms.</p>

CC BY-SA 3.0
2012-03-14T17:58:34.880Z
I don't see the direct connection to independent sets in that section although in a later section they have a reference to bisplit graphs (graphs that can be paritioned into an independent set and complete graph). I don't think I am looking for this!! Am I missing a connection?
v s
CC BY-SA 3.0
2012-03-14T22:54:50.127Z
@vs how about: for $G = (V, E)$, for every $u \in V$, have variable $x_u$, and for every $(u, v) \in E$ have clause $\neg x_u \vee \neg x_v$. all variables set to true correspond to an independent set.
Sasho Nikolov
CC BY-SA 3.0
2012-03-28T00:20:38.400Z
Is there a similar technique for coloring?
v s
CC BY-SA 3.0
2013-05-17T11:12:55.880Z
@vs Yes, same construction with a larger domain size.
Tyson Williams
CC BY-SA 3.0
2012-03-14T08:11:52.303Z
2012-03-14T08:11:52.303Z
Andreas Björklund
<p>What algorithms/mathematical techniques are available to exactly/approximately count number of independent sets?</p>

<p>Is/Are there a good reference/good references on this topic?</p>

<p>I am interested in regular graphs.</p>

CC BY-SA 3.0
2012-03-14T07:51:44.130Z
Googling "counting independent sets regular graphs" yields [this recent paper](http://web.mit.edu/yufeiz/www/papers/indep_reg.pdf) as third result, which gives an upper bound.
Anthony Labarre
<ds.algorithms><reference-request><graph-theory><approximation-algorithms><counting-complexity>
counting independent sets
v s
# counting independent sets

(Asked by: username_0 on 2012-03-13)

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.

**Tags:** ds.algorithms, reference-request, graph-theory, approximation-algorithms, counting-complexity
> **Comments:**
> **username_1**: Googling "counting independent sets regular graphs" yields [this recent paper](http://web.mit.edu/yufeiz/www/papers/indep_reg.pdf) as third result, which gives an upper bound.  

---

## 3 answers

### Answer by username_4 on 2012-03-14. Score: 9 | Accepted answer

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.

> **Comments:**
> **username_0**: I don't see the direct connection to independent sets in that section although in a later section they have a reference to bisplit graphs (graphs that can be paritioned into an independent set and complete graph). I don't think I am looking for this!! Am I missing a connection?  
> **username_5**: @vs how about: for $G = (V, E)$, for every $u \in V$, have variable $x_u$, and for every $(u, v) \in E$ have clause $\neg x_u \vee \neg x_v$. all variables set to true correspond to an independent set.  
> **username_0**: Is there a similar technique for coloring?  
> **username_3**: @vs Yes, same construction with a larger domain size.  

---

### Answer by username_2 on 2012-03-14. Score: 7

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.


---

### Answer by username_3 on 2012-03-14. Score: 6

To supplement the answer from @RJK, as of yesterday, there is a new "state of the art."

[Sly and Sun](http://arxiv.org/abs/1203.2602) 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)$.

> **Comments:**
> **username_0**: Do you know if these results hold for graphs with specific structure such as strong, weak (etc) products whose underlying graph is dergee less than 3 and which has the value of lambda less than the above?  
> **username_3**: @v These graphs are regular?  
> **username_0**: Yes. But does the results imply for all regular graphs, without caveat?? (I am thinking something analogous to this - we know it is NP hard to ML decode a linear code.. but it is very hard to show for specific non-trivial codes like RS codes and also it is known there are codes where ML decoding is easy) Of course it looks like the result here holds for all regular graphs.. but there are cases where symmetry of the graph may help as well and I don't see these graphs (in the paper) are assumed to have any symmetry at all!!  
> **username_3**: @v This result holds for all $d$-regular graphs. I don't know too much about coding theory.  Maybe you should ask a new question.  

---

