14
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Ryan Williams Feb 12 '11 at 17:54
  • $\begingroup$ 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? $\endgroup$ – Giorgio Camerani Feb 12 '11 at 17:58
  • $\begingroup$ @Walter, Counting variable assignments that satisfy a given 2SAT formula is #P-complete but 2SAT is in P. $\endgroup$ – Mohammad Al-Turkistany Feb 12 '11 at 18:17
  • $\begingroup$ @turkistany: Yes I already know that... $\endgroup$ – Giorgio Camerani Feb 12 '11 at 18:24
  • $\begingroup$ @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? $\endgroup$ – Giorgio Camerani Feb 12 '11 at 19:27
15
$\begingroup$

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<c<3/2$, 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<c<1/2$, 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. Computational Complexity 9(1): 52-72 (2000)

$\endgroup$
  • $\begingroup$ So the deduction is that #VC for cubic graphs is #P-complete because #IS is #P-complete? $\endgroup$ – delete000 Jan 28 '18 at 16:22
9
$\begingroup$

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".

$\endgroup$
  • 4
    $\begingroup$ BTW, Alan Sly proved polynomial time inapproximability for maximum degree=6 -- arxiv.org/abs/1005.5584 $\endgroup$ – Yaroslav Bulatov Feb 13 '11 at 22:22
  • 1
    $\begingroup$ @Yaroslav: Thanks for the reference. It looks like good reading! $\endgroup$ – RJK Feb 13 '11 at 22:48
9
$\begingroup$

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) 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 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 fails. This is a yet unpublished observation announced in a talk during the Dagstuhl Seminar Computational Counting.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – András Salamon Feb 17 '11 at 18:07
  • 1
    $\begingroup$ 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), who proved that counting independent sets cannot be done in time $\exp(o(n/\log^3 n))$ unless ETH fails. $\endgroup$ – Holger Feb 21 '11 at 17:10
8
$\begingroup$

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


(source: yaroslavvb.com)

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – András Salamon Feb 17 '11 at 18:10
  • $\begingroup$ @András It is the vertex set that is being complicated, not the edge set. $\endgroup$ – Tyson Williams Jul 6 '12 at 1:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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