# 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, 2012 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, 2012 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, 2012 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, 2012 at 23:42
• Can you edit the question so that people can understand what you want to ask without reading the comment? Jun 10, 2012 at 17:36

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