2
$\begingroup$

My question is simple: does any body know where can I find the proof that MAX CLIQUE is NP-HARD?

Remarks:

MAX CLIQUE is the decision problem defined as follows:Given a graph $G$ and $k>0$. Does the graph $G$ contain a maximum clique of size $k$?

I have been looking for a formal proof that MAX CLIQUE is NP-Hard, still I haven't found one. The book of Computers and Intractability (Michael Garey) in the final chapters mentions briefly that the full proof is on the phd thesis of Ernet Legget: http://dl.acm.org/citation.cfm?id=907661 . I couldn't find the copy of the book on the internet nor any survey whit the proof.

$\endgroup$
4
$\begingroup$

There is probably a proof in Karp's original paper. Here is a simple reduction from SAT. Given an instance $\varphi$ of SAT with $m$ clauses, construct an instance of MAX-CLIQUE as follows. For each clause $C$ and each literal $\ell$ appearing in $C$, there is a vertex $(C,\ell)$. Two vertices $(C_1,\ell_1),(C_2,\ell_2)$ are connected if $C_1 \neq C_2$ and $\ell_1 \neq \lnot \ell_2$. This has a clique of size $m$ iff $\varphi$ is satisfiable (exercise).

$\endgroup$
  • $\begingroup$ I studied this proof for the CLIQUE problem which is a bit different from MAX CLIQUE but of course the same proof works for the MAX CLIQUE :) I can't believe that i could not see that!! THANKS! $\endgroup$ – Mr. Ariel Mar 3 '16 at 1:41
2
$\begingroup$

The standard reduction from SATISFIABILITY to CLIQUE is outlined in Karp's classic paper, see page 97.

$\endgroup$
  • $\begingroup$ Presumably it's the very same reduction appearing in my answer. $\endgroup$ – Yuval Filmus Mar 3 '16 at 9:15
  • $\begingroup$ Of course! In fact I'd be quite interested in any other natural reductions. $\endgroup$ – András Salamon Mar 3 '16 at 9:45

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.