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.
8
$\begingroup$
$\endgroup$
-
1$\begingroup$ Googling "counting independent sets regular graphs" yields this recent paper as third result, which gives an upper bound. $\endgroup$ – Anthony Labarre Mar 14 '12 at 7:51
7
$\begingroup$
$\endgroup$
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.
answered Mar 14 '12 at 8:11
-
$\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 '12 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$ – Sasho Nikolov Mar 14 '12 at 22:54
-
-
$\begingroup$ @vs Yes, same construction with a larger domain size. $\endgroup$ – Tyson Williams May 17 '13 at 11:12
5
$\begingroup$
$\endgroup$
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.
4
$\begingroup$
$\endgroup$
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)$.
answered Mar 14 '12 at 17:13
-
$\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 '12 at 19:03
-
-
$\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 '12 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$ – Tyson Williams Mar 15 '12 at 12:54
