Proof that MAX CLIQUE is NP-Hard

Question

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.

Answer 1

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

Answer 2

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

• Richard M. Karp, Reducibility among Combinatorial Problems, In Proceedings of a symposium on the Complexity of Computer Computations, 1972, pp.85–103. doi:10.1007/978-1-4684-2001-2_9