In chapter of Hardness of Approximation in V. Vazirani's book it says:

For establishing a hardness of approximation result for, say, the vertex cover problem, PCP theorem is used to show the following polynomial time reduction. It maps an instance φ of SAT to a graph G = (V,E) such that

• if φ is satisfiable, G has a vertex cover of size ≤ 2/3*|V |, and

• if φ is not satisfiable, the smallest vertex cover in G is of size > α· 2/3*|V |,

Next line it claims:

Claim 29.1 As a consequence of the reduction stated above, there is no polynomial time algorithm for vertex cover that achieves an approximation guarantee of α, assuming P ≠ NP. (α>1)

I couldn't understand that claim, while in previous chapters it says Vertex Cover have 2-approximation algorithm (with Maximal matching).

Could anyone explain what does it means? How it obtained 2/3*|V|? and Why it said there is no α approximation while in previous chapters it proposed ones?

  • $\begingroup$ There is some context missing here. I have no idea what is the gap-introducing reduction stated above. $\endgroup$ – Yuval Filmus Jun 26 '17 at 12:21
  • $\begingroup$ @YuvalFilmus Thanks for your comment, I added more details. $\endgroup$ – Amir Jun 26 '17 at 15:46
  • $\begingroup$ Presumably they meant ​ "assuming P≠NP" ​ rather than ​ "assuming P=NP" . ​ ​ ​ ​ $\endgroup$ – user12859 Jun 26 '17 at 15:58
  • $\begingroup$ Are you sure you've copied down the text of "Claim 29.1" precisely, word-for-word? Please check down your copying it it carefully. I suspect you've copied it down wrong, or are missing some context. $\endgroup$ – D.W. Jun 27 '17 at 21:18
  • $\begingroup$ @D.W. I double check, book is publicly available at www.cc.gatech.edu/~vazirani/Vazirani.pdf $\endgroup$ – Amir Jun 28 '17 at 4:56

We can proof this claim by contradiction. If there exists an α-approximation algorithm for Vertex Cover, we will be able to use it for solving SAT problem in polynomial time and it's a contradiction by giving P≠NP.

We assume that there exists a gap introducing reduction that converts an instance of SAT to an instance of Vertex Cover giving:

• if φ is satisfiable, OPT(VC) ≤ 2/3 * |V|, and

• if φ is not satisfiable, OPT(VC) > α * 2/3 * |V|.

We can use this reduction and convert φ to I(VC) in polynomial time, then use the α-approximation algorithm for Vertex Cover in polynomial time and calculate objective function value (we call it f) for it.

As we know value of f stands between two bounds:

OPT(VC) ≤ f ≤ α*OPT(VC)

After that, we can use f to make a decision about φ satisfaction state:

If f ≤ α * 2/3 * |V|, then yes, else no.

We claim that if f is less than α * 2/3 * |V|, φ should be satisfiable because if φ isn't satisfiable, f can't be less than α * 2/3 * |V| which is lower bound to OPT(VC) (according to reduction assumptions) and objective function value can't be less than optimum.

Also we claim that if f is greater than α * 2/3 * |V|, φ shouldn't be satisfiable because if φ is satisfiable, it violates the approximation inequality. (f ≤ α*OPT(VC))

  • $\begingroup$ Thanks for your clarification. I could understand proof and I completely agree with that. My question is Why it said no approximation algorithm exist while in previous chapters it proposed ones (maximal matching with approximation factor of 2). How it find 2/3|V| as a proper function? why not choose another e.g 4/3|V|? $\endgroup$ – Amir Jun 26 '17 at 9:32
  • $\begingroup$ There is a gap-introducing reduction from SAT to VC. It's described in a paper of Dinur and Safra. $\endgroup$ – Yuval Filmus Jun 26 '17 at 12:23
  • $\begingroup$ @Amir The 2-approximation algorithm which is proposed in Vazirani book for Vertex Cover does not regard gap introducing constraints. $\endgroup$ – aminography Jun 26 '17 at 17:00

Yeah, that is a bit confusing. The bottom line is that you've misunderstood the surrounding context, and consequently, you've misunderstood what the claim is saying.

The previous sentence before Claim 29.1 is basically saying: "Suppose there exists a reduction from SAT to vertex cover with a particular property based on $\alpha$." Then, Claim 29.1 is saying "If such a reduction exists, then you can't approximate vertex cover to approximation ratio $\alpha$." Whether such a reduction exists will depend on the particular value of $\alpha$. Claim 29.1 is not saying that there is no approximation for vertex cover for any $\alpha > 1$; it's just saying there's no approximation for $\alpha$, if there's a gap-preserving reduction with parameter $\alpha$. Thus, the claim will apply to some values of $\alpha$, but not necessarily all values of $\alpha$.

This becomes particularly clear once you read the proof of Claim 29.1 (which immediately follow the statement of the claim). I agree that the wording in the book is a bit confusing and could be clearer. Fortunately, in this case you can figure out what was meant from context by reading the proof of the claim.

Here's what is true:

  • Vertex Cover has a 2-approximation.

  • There is no $\alpha$-approximation for $\alpha \le 1.3606$ (unless P=NP).

  • No one knows of an $\alpha$-approximation with $\alpha<2$ (though we don't have a proof that it doesn't exist; this could always represent a lack of imagination on our part).

The claim "Vertex Cover has no $\alpha$-approximation for any $\alpha>1$" is false; for instance, it does have a $\alpha$-approximation for $\alpha=2$, using maximal matching (as you said).

Ultimately there is no contradiction among all of this, and it doesn't contradict Claim 29.1, once you understand what Claim 29.1 is trying to say.


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.