5
$\begingroup$

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

$\endgroup$

1 Answer 1

13
$\begingroup$

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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.