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$
  • 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. Dec 12 '15 at 3:12
  • $\begingroup$ plz cite the thm! $\endgroup$ – vzn Dec 12 '15 at 17:08
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$
  • $\begingroup$ What insight does this give me on the decision version of the problem.? Just curious... $\endgroup$ – ARi Dec 12 '15 at 15:20
  • $\begingroup$ @ARi It implies it's NP-hard. $\endgroup$ – Yuval Filmus Dec 12 '15 at 19:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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