6
$\begingroup$

I read a theorem which states that: If there exists a polynomial time approximation algorithm for solving the Maximum Clique problem (or the Maximum Independent Set problem) for any constant performance ratio r, then NP = P.

But I never understood the reasoning behind this!!

$\endgroup$
3
  • 2
    $\begingroup$ What research have you done? Where have you looked? You might take a look at the Wikipedia page on the clique problem, which has some pointers to where you can find more. It looks like the results follow from results on PCP, which are non-trivial. I don't know if there's a more elementary proof. $\endgroup$
    – D.W.
    Commented Dec 12, 2015 at 3:12
  • $\begingroup$ plz cite the thm! $\endgroup$
    – vzn
    Commented Dec 12, 2015 at 17:08
  • $\begingroup$ update: this article(arxiv.org/abs/1909.04396) claimed a 2-approximation algorithm for MAX-CLIQUE. $\endgroup$
    – Mengfan Ma
    Commented Feb 22, 2020 at 1:57

1 Answer 1

9
$\begingroup$

In fact, something stronger is true: if you can approximate maximum clique within $n^{1-\epsilon}$ for some $\epsilon > 0$ then P=NP. This is because for every $\epsilon > 0$ there is a polytime reduction $f_\epsilon$ that takes an instance $\varphi$ of SAT and returns an instance $(G,cn)$ of maximum clique such that:

  1. If $\varphi$ is satisfiable then $G$ has a $cn$-clique.
  2. If $\varphi$ is not satisfiable then $G$ has no $cn^{1-\epsilon}$-clique.

If you could approximate maximum clique within $n^{1-\epsilon}$ you would be able to distinguish the two cases (exercise), and so to decide whether $\varphi$ is satisfiable or not.

The reduction uses the PCP theorem as a first ingredient. Given the PCP theorem it is not hard to give a similar reduction with a constant gap, and with some effort to give a reduction with a gap of $n^\epsilon$ for some $\epsilon > 0$. The reduction claimed above, which has a gap of $n^{1-\epsilon}$ for every $\epsilon>0$, is much harder. See lecture notes of Guruswami and O'Donnell for the constant gap, and lecture notes of Scheideler for the $n^\epsilon$ gap.

$\endgroup$
2
  • $\begingroup$ What insight does this give me on the decision version of the problem.? Just curious... $\endgroup$
    – ARi
    Commented Dec 12, 2015 at 15:20
  • $\begingroup$ @ARi It implies it's NP-hard. $\endgroup$ Commented Dec 12, 2015 at 19:53

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.