If you want to make money online : Register now

[Solved]: Proof that MAX CLIQUE is NP-Hard

, , No Comments
Problem Detail: 

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


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.

Asked By : Mr. Ariel

Answered By : Yuval Filmus

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/53917

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback