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?
$\begingroup$
$\endgroup$
1
-
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 RicherbyApr 4, 2014 at 7:13
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
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.
answered Apr 4, 2014 at 4:29
-
$\begingroup$ Can you explain me a bit more the sixth line, where you count the covers of size 3(nl+1)? $\endgroup$– ParamarApr 27, 2014 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$ Apr 27, 2014 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$– ParamarApr 14, 2015 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$ Apr 14, 2015 at 13:39