Tell me more ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.
up vote 8 down vote favorite

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.

share|improve this question
1  
Googling "counting independent sets regular graphs" yields this recent paper as third result, which gives an upper bound. – Anthony Labarre Mar 14 '12 at 7:51

3 Answers

up vote 6 down vote accepted

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.

share|improve this answer
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 Mar 14 '12 at 17:58
4  
@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 Mar 14 '12 at 22:54
Thankyou! Got the connection! – v s Mar 15 '12 at 0:47
Is there a similar technique for coloring? – v s Mar 28 '12 at 0:20
@vs Yes, same construction with a larger domain size. – Tyson Williams May 17 at 11:12
up vote 5 down vote

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.

share|improve this answer
up vote 4 down vote

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

share|improve this answer
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 Mar 14 '12 at 19:03
@v These graphs are regular? – Tyson Williams Mar 15 '12 at 1:21
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 Mar 15 '12 at 1:24
1  
@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 Mar 15 '12 at 12:54
Thankyou. Interesting. – v s Mar 15 '12 at 15:38

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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