4
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ I don't see why this would make counting any easier: you're not actually approximating anything. Instead of just having to exactly count minimum-size solutions, you now have to exactly count those and exactly count a set of larger vertex covers, too. That seems doomed. For the optimization problem ("What is the size of smallest vertex cover?"), this can help because you're allowing yourself an approximation factor in the answer. But in the counting problem, you're just giving yourself more things to count, while still demanding that the answer be exact. Why would that be easier? $\endgroup$ – David Richerby Apr 4 '14 at 7:13
5
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Can you explain me a bit more the sixth line, where you count the covers of size 3(nl+1)? $\endgroup$ – Paramar Apr 27 '14 at 16:34
  • 1
    $\begingroup$ @Paramar It's a rough upper bound. A vertex cover needs to contain $n\ell$ vertices among the $n$ copies of $G$, and $3n\ell+3$ in total, so at most $2n\ell+3$ can belong to the clique. This gives us $\binom{n^2}{3n\ell+3}\binom{n^D}{2n\ell+3}$ as a rough upper bound (more accurately, you would need to take $\sum_{t_1 \leq 3n\ell+3} \sum_{t_2 \leq 2n\ell+3} \binom{n^2}{t_1} \binom{n^D}{t_2}$, but this is well-approximated by the expression I wrote). This is a growing function of $\ell$, so since $\ell \leq k$ we can replace $\ell$ with $k$. $\endgroup$ – Yuval Filmus Apr 27 '14 at 16:42
  • $\begingroup$ In the sixth line again: As you choose $3nk+3$ from $n^2$ and $2nk+3$ from $n^D$ shouldn't the cover have a size of $5nl+6$? $\endgroup$ – Paramar Apr 14 '15 at 13:16
  • 1
    $\begingroup$ @Paramar Possibly. This is an answer from last year, so your guess is as good as mine. In papers you often see small mistakes, which are often, though not always, corrigible. Just work it out yourself. $\endgroup$ – Yuval Filmus Apr 14 '15 at 13:39

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.