3
$\begingroup$

Assume that UG is $\mathsf{NPI}$, i.e. not solvable in $\mathsf{P}$ nor in $\mathsf{NP\text{-}complete}$ (so UGC is false). Is it still NP-hard to give a $(2-\epsilon)$ polytime approximation algorithm for Vertex Cover, for example? If not, where does the new threshold of NP-hardness move in $(1,2-\epsilon]$?

$\endgroup$
10
  • 4
    $\begingroup$ Hint: See a blog post by Lance Fortnow about UG-hardness. $\endgroup$ – Tsuyoshi Ito Jun 6 '12 at 18:08
  • $\begingroup$ Thank you Tsuyoshi, but I think the specific blog post is not related too much on a possible relation of UG with the NPI class, concerning inapproximability. $\endgroup$ – NicosM Jun 6 '12 at 18:41
  • 5
    $\begingroup$ Nicos, the post actually is all about your question. In short, if UG is not in P, then there is no poly time algorithm which approximates max cut better than GW, etc. $\endgroup$ – Sasho Nikolov Jun 6 '12 at 19:07
  • 3
    $\begingroup$ That is the point of Lance's post: approximating MaxCut better than the GW constant is UG-hard, and this is a valid statement no matter if UGs are NP-hard. In other words, there is a polytime reduction which shows that if one can approximate MaxCut better than the GW constant, then the approximation algorithm can be used to solve UG in polytime. So if you cannot solve UG in polytime, you cannot approximage MaxCut better than GW $\endgroup$ – Sasho Nikolov Jun 6 '12 at 23:42
  • 1
    $\begingroup$ Can you edit the question so that people can understand what you want to ask without reading the comment? $\endgroup$ – Tsuyoshi Ito Jun 10 '12 at 17:36
4
$\begingroup$

To address your revised question:

If UGC is false, is it still NP-hard to give a $(2-\epsilon)$ polytime approximation algorithm for Vertex Cover?

If it were known that it is NP-hard to approximate VC better than a factor of 2, even if the UGC is false, then we would unconditionally know that approximating VC to a factor better than 2 is NP-hard. This also works with a factor smaller than 2. If it were known that if UGC is false, then VC is NP-hard to approximate better than a factor of (say) 1.5, then we would know that it is (unconditionally) NP-hard to approximate it better than a factor of 1.5.

Since we don't know that, I guess the best we can say if the UGC is false is that it's NP-hard to approximate it to within a factor of 1.3606 by the result of Dinur and Safra (2005). (I think that's the current best-known inapproximability result.)

$\endgroup$
1
  • $\begingroup$ The first paragraph seems like a tautology, and I am not sure what it is supposed to explain. I like the second paragraph. $\endgroup$ – Tsuyoshi Ito Jun 12 '12 at 14:44

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.