Counting approximate solutions

Many of us are familiar with the $P$ class. Counting solutions is believed to be a difficult task and that is why we usually end up approximating the number of solutions (we relax the accuracy of the counting). I want to ask, if relaxing the quality of the solutions counted has been addressed as a problem. Is there for example, any algorithms able to answer the question: How many vertex covers there are, with 3 times the cardinality of the minimum vertex cover? Is the problem $P-$ complete?

Let $(G,k)$ be an instance of vertex cover, where $G$ is a graph on $n$ vertices, and $k$ is the threshold. Suppose furthermore that the minimum vertex cover of $G$ has size either at most $k$ or at least $ck$ for some $c > 1$; this version is already NP-hard.

Consider $n$ copies of $G$, with the addition of a clique of size $n^D$. If $G$ has a minimum vertex cover of size $\ell \leq k$ then the new graph has a vertex cover of size $n\ell+1$, and at most $\binom{n^2}{3nk+3} \binom{n^D}{2nk+3} \leq n^{(6+2D)nk + 6+3D}$ vertex covers of size $3(n\ell+1)$. If the minimum vertex cover of $G$ is $\ell \geq ck$ then the new graph has a minimum vertex cover of $n\ell+1$, and at least $\binom{n^D}{2n(ck)+3} \approx n^{2Dcnk+3D}$ vertex covers of size $3(n\ell+1)$. We can choose $D$ so that $2Dc > 6+2D$, and then the gap between the two cases is roughly $n^{(2Dc-2D-6)nk-6} = e^{\Omega(n\log n)}$.

This reduction shows that it is NP-hard to approximate the number of vertex covers of thrice the minimum size within $e^{O(n\log n)}$. The interested reader can get even better results by slightly tweaking the construction.

StackExchange Computer Science Q#23409, answer score: 5