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