3

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]$?

NicosM
  • 47
  • 4
  • 4
    Hint: See a blog post by Lance Fortnow about UG-hardness. – Tsuyoshi Ito Jun 06 '12 at 18:08
  • 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. – NicosM Jun 06 '12 at 18:41
  • 5
    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. – Sasho Nikolov Jun 06 '12 at 19:07
  • Sasho this is if UG is NP-hard. If UG is neither NP-hard nor in P, how do you know that? The conjecture clearly talks about the NP-hardness of unique games. – NicosM Jun 06 '12 at 19:11
  • It would help if you are more specific about "the inapproximability results". Also what do you mean exactly by preserved? Do you mean we obtain exactly the same consequences? – Kaveh Jun 06 '12 at 21:42
  • For example, whether the $(2-\epsilon)$ threshold for VC still holds, or the $0.878+\epsilon$ for Max-Cut. – NicosM Jun 06 '12 at 22:01
  • 3
    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 – Sasho Nikolov Jun 06 '12 at 23:42
  • 1
    Can you edit the question so that people can understand what you want to ask without reading the comment? – Tsuyoshi Ito Jun 10 '12 at 17:36
  • What do you mean by “threshold of NP-hardness”? If you mean the boundary of approximation ratio between being NP-hard and not being NP-hard, then it should be obvious that without UGC, the results assuming UGC do not tell us anything about the boundary, and we do not know the exact value of the boundary without UGC. – Tsuyoshi Ito Jun 10 '12 at 23:54
  • Yes that's what I mean. Therefore, he boundary stays 'somewhere' in [1.36,2-$\epsilon]$ and we can not deduce it, even if it is proved that $UG\in NPI$. – NicosM Jun 11 '12 at 00:23

1 Answers1

4

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

Robin Kothari
  • 13,617
  • 2
  • 60
  • 116
  • The first paragraph seems like a tautology, and I am not sure what it is supposed to explain. I like the second paragraph. – Tsuyoshi Ito Jun 12 '12 at 14:44