For which values $A,B$ is the problem $\mathsf{gap\mathord-VC}\mathord-[A,B]$ NP-hard? VC is the vertex cover problem. I am given three options: $B=\frac{3}{4},A=\frac{1}{2}$ or $B=\frac{3}{4},A=\frac{1}{4}$ or none.

I would to review what I think that I need to do, I'm not sure that the way I think of it is correct. This is what I think: I need to decide if it NP-hard to approximate the VC to $\frac{1}{2}$, i.e., can I build an NP Turing machine that would return Yes iff for a given graph, it can guarantee that it has less than $\frac{1}{4}V$ vertices that cover the whole graph? Maybe even for $\frac{1}{2}V$ vertices?

This is a question from a past midterm that I'm solving now in order to prepare myself for my own midterm in a "Computational Complexity Theory" course.

  • $\begingroup$ Can you define the gap-VC-[$A,B$] problem? $\endgroup$ – Yuval Filmus Dec 12 '12 at 20:39

Vertex cover has an easy $2$-approximation, so gap-VC-[$1/4,3/4$] is easy. The best unconditional hardness result is by Dinur and Safra, which gives $1.3606$ hardness. Since $(3/4)/(1/2) = 1.5 > 1.3606$, their method definitely doesn't imply gap-VC-[$1/2,3/4$]-hardness. Assuming the Unique Games Conjecture, the hardness of vertex cover is $2-\epsilon$, but this doesn't necessarily imply that gap-VC-[$1/2,3/4$] is hard - you'd have to look at the proof to determine that.

In summary, I have no idea what the correct answer is, and I'm not sure that anyone else knows which answer is correct (unconditionally).

| cite | improve this answer | |

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.