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.
Proof that MAX CLIQUE is NP-Hard
complexity theory;np hard;decision problem;np
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).