<p>Following on Yaroslav's answer, Luby and Vigoda were the first to show a FPRAS for #IS under a density condition (maximum degree 4, which I suppose is weaker than Weitz's result), while Dyer, Frieze and Jerrum showed that there is no FPRAS for #IS if the maximum degree of the graph is 25 unless RP = NP.</p>

<p>References:</p>

<p>Martin Dyer, Alan Frieze, and Mark Jerrum. On counting independent sets in sparse graphs. FOCS 1999.</p>

<p>Michael Luby and Eric Vigoda. Approximately counting up to four. STOC 1997.</p>

<p>See also Jerrum's ETH lecture notes, "Counting, sampling and integrating: algorithms and complexity".</p>

CC BY-SA 2.5
2011-02-13T22:22:40.163Z
BTW, Alan Sly proved polynomial time inapproximability for maximum degree=6 -- arxiv.org/abs/1005.5584
Yaroslav Bulatov
CC BY-SA 2.5
2011-02-13T22:48:16.360Z
@Yaroslav: Thanks for the reference.  It looks like good reading!
RJK
CC BY-SA 2.5
2011-02-13T00:04:13.360Z
2011-02-13T00:33:00.773Z
2011-02-13T00:33:00.773Z
RJK
<p>With respect to exponential time complexity, general instances and instances with constant maximum degree are equally hard: The sparsification lemma of <a href="http://dx.doi.org/10.1109/SFCS.1998.743516" rel="noreferrer">Impagliazzo, Paturi, Zane (2002)</a> shows that $n$-variable instances of $d$-Sat can be reduced to instances of $d$-Sat with at most $f(d,\epsilon)\cdot n$ clauses in time $\exp(\epsilon n)$. As observed in <a href="http://dx.doi.org/10.1007/978-3-642-14165-2" rel="noreferrer">joint work</a> with Husfeldt and Wahlén, the sparsification lemma works for the counting versions of $d$-Sat, too, and especially for the case of counting $2$-Sat (which is equivalent to counting independent sets and counting vertex covers).</p>

<p>Moreover, counting independent sets in an $n$-vertex graph cannot be done in time $\exp(o(n))$ unless the <a href="http://en.wikipedia.org/wiki/Exponential_time_hypothesis" rel="noreferrer">exponential time hypothesis</a> fails. This is a yet unpublished observation announced in <a href="http://www.dagstuhl.de/Materials/Files/10/10481/10481.DellHolger.Slides.pdf" rel="noreferrer">a talk</a> during the Dagstuhl Seminar <a href="http://www.dagstuhl.de/10481" rel="noreferrer">Computational Counting</a>.</p>

CC BY-SA 2.5
2011-02-17T18:07:36.513Z
regarding your final comment:  ETH means that SAT cannot be solved in subexponential time, which by standard reductions implies that INDEPENDENT SET cannot be decided in subexponential time either.  It is then immediate that ETH implies counting independent sets also cannot be done in subexponential time.
András Salamon
CC BY-SA 2.5
2011-02-21T17:10:51.937Z
Deciding and counting the number of _maximum_ independent sets is hard under ETH via some known standard reduction from 3SAT. However, this question was about counting _all_ (i.e., not necessarily maximum) independent sets in a graph. The decision version is trivial: the empty set is always an independent set. Compare also [Hoffmann (2010)](http://arxiv.org/abs/1007.1146), who proved that counting independent sets cannot be done in time $\exp(o(n/\log^3 n))$ unless ETH fails.
Holger
CC BY-SA 2.5
2011-02-13T15:16:47.673Z
2011-02-13T15:16:47.673Z
Holger
<p>Set is a vertex cover iff its complement is an independent set, therefore this problem is equivalent to counting independent sets.</p>
<p>Algebraic counting of independent sets is FPT for graphs of bounded bounded clique-width. For instance, see Courcelle's &quot;A multivariate interlace polynomial and its computation for graphs of bounded clique-width&quot;, where they compute a generalization of independence polynomial. Adding up coefficients of independence polynomial gives the number of independent sets.</p>
<p>Graphs with maximum degree 3 can have unbounded clique-width.</p>
<p>Numerical counting of independent sets is tractable when the problem exhibits &quot;correlation decay&quot;. Dror Weitz (<a href="http://dimacs.rutgers.edu/~dror/pubs/ind_from_tree.pdf" rel="nofollow noreferrer">STOC'06</a>) gives a deterministic FPTAS for counting weighted independent sets on graphs of maximum degree <span class="math-container">$d$</span> when the weight <span class="math-container">$\lambda$</span> is</p>
<p><span class="math-container">$$\lambda&lt;\frac{(\Delta-1)^{\Delta-1}}{(\Delta-2)^\Delta}$$</span></p>
<p><a href="https://i.sstatic.net/Tovoq.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/Tovoq.png" alt="" /></a><br />
<sub>(source: <a href="http://yaroslavvb.com/upload/save/weitz.png" rel="nofollow noreferrer">yaroslavvb.com</a>)</sub></p>
<p>Regular (unweighted) independent set counting corresponds to <span class="math-container">$\lambda=1$</span> so his algorithm gives FPTAS for number of vertex covers on graphs of maximum degree 5.</p>
<p>His algorithm is based on building a self-avoiding walk tree at each vertex, and truncating this tree at depth <span class="math-container">$d$</span>. Branching factor of self-avoiding walk trees determines the range of <span class="math-container">$\lambda$</span> for which small depth <span class="math-container">$d$</span> gives a good approximation, and formula above is derived by using maximum degree of the graph to upper bound this branching factor.</p>

CC BY-SA 3.0
2012-07-06T01:58:42.627Z
@András It is the vertex set that is being complicated, not the edge set.
Tyson Williams
CC BY-SA 2.5
2011-02-17T18:10:24.577Z
The problem with working with IS instead of VC is that the complement graphs may lose some nice properties one wants: for instance, "bounded degree at most k" becomes "with degree at least n-k", which is now dependent on the instance size.  This may or may not be relevant.
András Salamon
CC BY-SA 4.0
2011-02-12T22:44:44.537Z
2019-02-22T20:12:31.193Z
2020-06-17T09:38:08.363Z
Yaroslav Bulatov
<p>The #VC problem of computing the number of vertex covers of a given graph remains #P-hard for 3-regular graphs; see for example [Greenhill, 2000].</p>

<p>To show that the #VC problem remains #P-hard for graphs with at most <span class="math-container">$c\cdot n$</span> edges, where <span class="math-container">$n$</span> is the number of vertices and <span class="math-container">$0&lt;c&lt;3/2$</span>, reduce from the 3-regular case by adding a large enough independent set (of linear size). The number of vertex covers remains the same if you add an independent set.</p>

<p>Similarly, to show that the #VC problem remains #P-hard for graphs with at least <span class="math-container">$c\cdot n^2$</span> edges, where <span class="math-container">$n$</span> is the number of vertices and <span class="math-container">$0&lt;c&lt;1/2$</span>, reduce from #VC by adding a large enough clique component (of linear size). The number of vertex covers is multiplied by <span class="math-container">$p+1$</span> if you add a clique of size <span class="math-container">$p$</span> to a graph.</p>

<p>Catherine S. Greenhill: <a href="https://doi.org/10.1007/PL00001601" rel="nofollow noreferrer">The complexity of counting colourings and independent sets in sparse graphs and hypergraphs</a>. Computational Complexity 9(1): 52-72 (2000)</p>

CC BY-SA 3.0
2018-01-28T16:22:49.693Z
So the deduction is that #VC for cubic graphs is #P-complete because #IS is #P-complete?
delete000
CC BY-SA 4.0
2011-02-12T22:35:26.447Z
2019-02-24T16:39:14.000Z
2019-02-24T16:39:14.000Z
Serge Gaspers
<p>Consider the #P-complete problem of counting the number of vertex covers of a given graph $G = (V, E)$.</p>

<p>I'd like to know if there is any result showing how the hardness of such problem varies with some parameter of $G$ (for example, $d = \frac{|E|}{|V|}$).</p>

<p>My sensation is that the problem should be easier both when $G$ is sparse and when $G$ is dense, while it should be hard when $G$ is "in the middle". Is this really the case?</p>

CC BY-SA 2.5
2011-02-12T17:54:23.190Z
Do you want to count all vertex covers, or all minimum cardinality vertex covers? Note the first problem may be easier in some cases, as it's not necessarily helping you solve an NP-complete problem.
Ryan Williams
CC BY-SA 2.5
2011-02-12T17:58:31.640Z
Hi Ryan, yes I want to count all vertex covers. Why you say _"it's not necessarily helping you solve a NP-complete problem"_? If it is #P-complete, why it doesn't help me solving NP-complete problems?
Giorgio Camerani
CC BY-SA 2.5
2011-02-12T18:17:32.217Z
@Walter, Counting variable assignments that satisfy a given 2SAT formula is #P-complete but 2SAT is in P.
Mohammad Al-Turkistany
CC BY-SA 2.5
2011-02-12T18:24:10.800Z
@turkistany: Yes I already know that...
Giorgio Camerani
CC BY-SA 2.5
2011-02-12T19:27:11.527Z
@turkistany: ...but then? Whatever NP-complete problem I have, I can convert it to SAT, then SAT to #SAT, then #SAT to #Monotone-2SAT (which is exactly the same as counting vertex covers). So why I shouldn't be able to solve NP-complete problems, given the ability to count vertex covers?
Giorgio Camerani
CC BY-SA 2.5
2011-02-13T16:34:43.747Z
It's clear that counting minimum cardinality vertex covers is hard, because finding any minimum vertex cover is a hard problem. But finding any vertex cover at all is trivial, and in some cases, the counting version of an easy problem is *not* #P-complete, but also easy. For instance, in graphs of degree at most 2 (as opposed to 3), counting vertex covers remains easy.
Ryan Williams
CC BY-SA 2.5
2011-02-13T17:30:04.900Z
@Ryan: I do not think that your example works because counting minimum cardinality vertex covers is also easy in graphs of degree at most 2.  Am I missing something?
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-14T01:59:47.897Z
I don't know what it would mean for an example to "work" or "not work" here. You are giving yet another example where the "finding" version and "counting" version are both easy. I was just making the trivial point that counting all objects when finding one of them is easy does not necessarily solve an NP-complete problem, while counting all objects when finding one is hard is definitely solving an NP-complete problem.
Ryan Williams
<cc.complexity-theory><graph-theory><counting-complexity><time-complexity>
Counting the number of vertex covers: when is it hard?
Giorgio Camerani
# Counting the number of vertex covers: when is it hard?

(Asked by: username_0 on 2011-02-12)

Consider the #P-complete problem of counting the number of vertex covers of a given graph $G = (V, E)$.

I'd like to know if there is any result showing how the hardness of such problem varies with some parameter of $G$ (for example, $d = \frac{|E|}{|V|}$).

My sensation is that the problem should be easier both when $G$ is sparse and when $G$ is dense, while it should be hard when $G$ is "in the middle". Is this really the case?

**Tags:** cc.complexity-theory, graph-theory, counting-complexity, time-complexity

> **Comments:**
> **username_1**: Do you want to count all vertex covers, or all minimum cardinality vertex covers? Note the first problem may be easier in some cases, as it's not necessarily helping you solve an NP-complete problem.  
> **username_0**: Hi Ryan, yes I want to count all vertex covers. Why you say _"it's not necessarily helping you solve a NP-complete problem"_? If it is #P-complete, why it doesn't help me solving NP-complete problems?  
> **username_2**: @Walter, Counting variable assignments that satisfy a given 2SAT formula is #P-complete but 2SAT is in P.  
> **username_0**: @turkistany: Yes I already know that...  
> **username_0**: @turkistany: ...but then? Whatever NP-complete problem I have, I can convert it to SAT, then SAT to #SAT, then #SAT to #Monotone-2SAT (which is exactly the same as counting vertex covers). So why I shouldn't be able to solve NP-complete problems, given the ability to count vertex covers?  
> **username_1**: It's clear that counting minimum cardinality vertex covers is hard, because finding any minimum vertex cover is a hard problem. But finding any vertex cover at all is trivial, and in some cases, the counting version of an easy problem is *not* #P-complete, but also easy. For instance, in graphs of degree at most 2 (as opposed to 3), counting vertex covers remains easy.  
> **username_3**: @Ryan: I do not think that your example works because counting minimum cardinality vertex covers is also easy in graphs of degree at most 2.  Am I missing something?  
> **username_1**: I don't know what it would mean for an example to "work" or "not work" here. You are giving yet another example where the "finding" version and "counting" version are both easy. I was just making the trivial point that counting all objects when finding one of them is easy does not necessarily solve an NP-complete problem, while counting all objects when finding one is hard is definitely solving an NP-complete problem.  

---

## 4 answers

### Answer by username_9 on 2011-02-12. Score: 15 | Accepted answer

The #VC problem of computing the number of vertex covers of a given graph remains #P-hard for 3-regular graphs; see for example [Greenhill, 2000].

To show that the #VC problem remains #P-hard for graphs with at most $c\cdot n$ edges, where $n$ is the number of vertices and $0, reduce from the 3-regular case by adding a large enough independent set (of linear size). The number of vertex covers remains the same if you add an independent set.

Similarly, to show that the #VC problem remains #P-hard for graphs with at least $c\cdot n^2$ edges, where $n$ is the number of vertices and $0, reduce from #VC by adding a large enough clique component (of linear size). The number of vertex covers is multiplied by $p+1$ if you add a clique of size $p$ to a graph.

Catherine S. Greenhill: [The complexity of counting colourings and independent sets in sparse graphs and hypergraphs](https://doi.org/10.1007/PL00001601). Computational Complexity 9(1): 52-72 (2000)

> **Comments:**
> **username_10**: So the deduction is that #VC for cubic graphs is #P-complete because #IS is #P-complete?  

---

### Answer by username_4 on 2011-02-13. Score: 9

Following on Yaroslav's answer, Luby and Vigoda were the first to show a FPRAS for #IS under a density condition (maximum degree 4, which I suppose is weaker than Weitz's result), while Dyer, Frieze and Jerrum showed that there is no FPRAS for #IS if the maximum degree of the graph is 25 unless RP = NP.

References:

Martin Dyer, Alan Frieze, and Mark Jerrum. On counting independent sets in sparse graphs. FOCS 1999.

Michael Luby and Eric Vigoda. Approximately counting up to four. STOC 1997.

See also Jerrum's ETH lecture notes, "Counting, sampling and integrating: algorithms and complexity".

> **Comments:**
> **username_5**: BTW, Alan Sly proved polynomial time inapproximability for maximum degree=6 -- arxiv.org/abs/1005.5584  
> **username_4**: @Yaroslav: Thanks for the reference.  It looks like good reading!  

---

### Answer by username_6 on 2011-02-13. Score: 9

With respect to exponential time complexity, general instances and instances with constant maximum degree are equally hard: The sparsification lemma of [Impagliazzo, Paturi, Zane (2002)](http://dx.doi.org/10.1109/SFCS.1998.743516) shows that $n$-variable instances of $d$-Sat can be reduced to instances of $d$-Sat with at most $f(d,\epsilon)\cdot n$ clauses in time $\exp(\epsilon n)$. As observed in [joint work](http://dx.doi.org/10.1007/978-3-642-14165-2) with Husfeldt and Wahlén, the sparsification lemma works for the counting versions of $d$-Sat, too, and especially for the case of counting $2$-Sat (which is equivalent to counting independent sets and counting vertex covers).

Moreover, counting independent sets in an $n$-vertex graph cannot be done in time $\exp(o(n))$ unless the [exponential time hypothesis](http://en.wikipedia.org/wiki/Exponential_time_hypothesis) fails. This is a yet unpublished observation announced in [a talk](http://www.dagstuhl.de/Materials/Files/10/10481/10481.Dellusername_6.Slides.pdf) during the Dagstuhl Seminar [Computational Counting](http://www.dagstuhl.de/10481).

> **Comments:**
> **username_7**: regarding your final comment:  ETH means that SAT cannot be solved in subexponential time, which by standard reductions implies that INDEPENDENT SET cannot be decided in subexponential time either.  It is then immediate that ETH implies counting independent sets also cannot be done in subexponential time.  
> **username_6**: Deciding and counting the number of _maximum_ independent sets is hard under ETH via some known standard reduction from 3SAT. However, this question was about counting _all_ (i.e., not necessarily maximum) independent sets in a graph. The decision version is trivial: the empty set is always an independent set. Compare also [Hoffmann (2010)](http://arxiv.org/abs/1007.1146), who proved that counting independent sets cannot be done in time $\exp(o(n/\log^3 n))$ unless ETH fails.  

---

### Answer by username_5 on 2011-02-12. Score: 8

Set is a vertex cover iff its complement is an independent set, therefore this problem is equivalent to counting independent sets.

Algebraic counting of independent sets is FPT for graphs of bounded bounded clique-width. For instance, see Courcelle's "A multivariate interlace polynomial and its computation for graphs of bounded clique-width", where they compute a generalization of independence polynomial. Adding up coefficients of independence polynomial gives the number of independent sets.

Graphs with maximum degree 3 can have unbounded clique-width.

Numerical counting of independent sets is tractable when the problem exhibits "correlation decay". Dror Weitz ([STOC'06](http://dimacs.rutgers.edu/~dror/pubs/ind_from_tree.pdf)) gives a deterministic FPTAS for counting weighted independent sets on graphs of maximum degree $d$ when the weight $\lambda$ is

$$\lambda<\frac{(\Delta-1)^{\Delta-1}}{(\Delta-2)^\Delta}$$

[![](https://i.sstatic.net/Tovoq.png)](https://i.sstatic.net/Tovoq.png)  
(source: [yaroslavvb.com](http://yaroslavvb.com/upload/save/weitz.png))

Regular (unweighted) independent set counting corresponds to $\lambda=1$ so his algorithm gives FPTAS for number of vertex covers on graphs of maximum degree 5.

His algorithm is based on building a self-avoiding walk tree at each vertex, and truncating this tree at depth $d$. Branching factor of self-avoiding walk trees determines the range of $\lambda$ for which small depth $d$ gives a good approximation, and formula above is derived by using maximum degree of the graph to upper bound this branching factor.

> **Comments:**
> **username_7**: The problem with working with IS instead of VC is that the complement graphs may lose some nice properties one wants: for instance, "bounded degree at most k" becomes "with degree at least n-k", which is now dependent on the instance size.  This may or may not be relevant.  
> **username_8**: @András It is the vertex set that is being complicated, not the edge set.  

---

