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.

  • 1
    $\begingroup$ Googling "counting independent sets regular graphs" yields this recent paper as third result, which gives an upper bound. $\endgroup$ Mar 14, 2012 at 7:51

3 Answers 3


The problem can be restated as a #2SAT. See


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

  • $\begingroup$ 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? $\endgroup$
    – v s
    Mar 14, 2012 at 17:58
  • 5
    $\begingroup$ @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. $\endgroup$ Mar 14, 2012 at 22:54
  • $\begingroup$ Is there a similar technique for coloring? $\endgroup$
    – v s
    Mar 28, 2012 at 0:20
  • $\begingroup$ @vs Yes, same construction with a larger domain size. $\endgroup$ May 17, 2013 at 11:12

For approximate counting, the following paper (also in APPROX-RANDOM 2011)


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)$.

  • $\begingroup$ 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? $\endgroup$
    – v s
    Mar 14, 2012 at 19:03
  • $\begingroup$ @v These graphs are regular? $\endgroup$ Mar 15, 2012 at 1:21
  • $\begingroup$ 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!! $\endgroup$
    – v s
    Mar 15, 2012 at 1:24
  • 1
    $\begingroup$ @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. $\endgroup$ Mar 15, 2012 at 12:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.