<p>As far as I know (and can interpret your question) no such result is known. 
There are two reasons:</p>

<p>1) Generally unique games hardness results (as well as NP hardness result) do not yield "instance based" hardness. That is, the UG-hardness result have the following flavor - "if the unique games conjecture is true then for problem $P$ no algorithm can get a better approximation ratio than $\alpha$, where $\alpha$ is the ratio that the canonical SDP achieves on $P$" </p>

<p>2) While the theta function  is an appealing algorithm, and yields a $\sqrt{n}$ approximation for independent set for random graphs, in the worst case its approximation ratio can be close to $n$ (am not sure what's the extreme example), which can of course be achieved trivially. In fact, Hastad has gave an NP-hardness result ruling out an $n^{1-\epsilon}$ approximation for independent set for every $\epsilon&gt;0$. So, even without the unique games conjecture, we know that essentially there is no non-trivial <i>worst case</i> approximation algorithm for this problem.</p>

<p>It would be very nice if there was a natural class of graphs where the theta function yields, say, an $O(\sqrt{n})$ approximation, and it is NP or UG hard to do better. I don't know of any such result.</p>

CC BY-SA 3.0
2015-03-31T04:48:58.040Z
2015-03-31T14:03:58.260Z
2015-03-31T14:03:58.260Z
Boaz Barak
<p>Unique Games results provide very interesting barriers to results through semidefinite programming. Lovasz theta ($\vartheta(G)$) function is an incarnation of SDP.</p>

<p>Is UG conjecture true $\iff \vartheta(G)$ is best approximation number for independence number $\alpha(G)$ of classes of graphs whose $\alpha(G)$ computation do not have efficient procedure if $P\neq NP$?</p>

<p>(I am adding $P\neq NP$ to avoid cases where other techniques such as Haemer's Bound gives better approximation).</p>

<semidefinite-programming><unique-games-conjecture>
Unique Games versus SDP procedures
Turbo
# Unique Games versus SDP procedures

(Asked by: username_0 on 2015-02-02)

Unique Games results provide very interesting barriers to results through semidefinite programming. Lovasz theta ($\vartheta(G)$) function is an incarnation of SDP.

Is UG conjecture true $\iff \vartheta(G)$ is best approximation number for independence number $\alpha(G)$ of classes of graphs whose $\alpha(G)$ computation do not have efficient procedure if $P\neq NP$?

(I am adding $P\neq NP$ to avoid cases where other techniques such as Haemer's Bound gives better approximation).

**Tags:** semidefinite-programming, unique-games-conjecture

---

## 1 answers

### Answer by username_1 on 2015-03-31. Score: 13 | Accepted answer

As far as I know (and can interpret your question) no such result is known.
There are two reasons:

1) Generally unique games hardness results (as well as NP hardness result) do not yield "instance based" hardness. That is, the UG-hardness result have the following flavor - "if the unique games conjecture is true then for problem $P$ no algorithm can get a better approximation ratio than $\alpha$, where $\alpha$ is the ratio that the canonical SDP achieves on $P$"

2) While the theta function is an appealing algorithm, and yields a $\sqrt{n}$ approximation for independent set for random graphs, in the worst case its approximation ratio can be close to $n$ (am not sure what's the extreme example), which can of course be achieved trivially. In fact, Hastad has gave an NP-hardness result ruling out an $n^{1-\epsilon}$ approximation for independent set for every $\epsilon>0$. So, even without the unique games conjecture, we know that essentially there is no non-trivial *worst case* approximation algorithm for this problem.

It would be very nice if there was a natural class of graphs where the theta function yields, say, an $O(\sqrt{n})$ approximation, and it is NP or UG hard to do better. I don't know of any such result.


---

