Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
Can you define the gap-VC-[$A,B$] problem? – Yuval Filmus Dec 12 '12 at 20:39
up vote 2 down vote accepted

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.