# Consequences of Unique Games being a NPI problem

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

• Hint: See a blog post by Lance Fortnow about UG-hardness. Jun 6 '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. Jun 6 '12 at 18:41
• 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. Jun 6 '12 at 19:07
• 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 Jun 6 '12 at 23:42
• Can you edit the question so that people can understand what you want to ask without reading the comment? Jun 10 '12 at 17:36

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