# Large Clique is in P or NP-complete? P != NP for hypothesis

I need to find a solution to the following question: The problem to find a "Large Clique" is in P or NP-complete (assuming P != NP)?

The "Large Clique" problem is the following: Given a graph G = (V, E), does it contain a clique of size at least |V |/2?

I was thinking to use the relationship between the problem to find a clique in G by using the problem to find a Vertex Cover on the complement graph.

What do you think, it could be the right approach?

-
Hint: add vertices to the graph to convert a clique of any other size into a clique of size $|V|/2$. –  Erick Wong Feb 21 '13 at 19:16

According to Garey and Johnson, Computers and Intractability, page 194, CLIQUE is NP-complete, and "the variant in which, for a given $r$, $0\lt r\lt1$, we are asked whether $G$ contains a clique of size $r|V|$ or more is NP-complete for any fixed value of $r$."

-

There is a very simple reduction to CLIQUE, which as Gerry cites is well-known to be NP-complete and almost certainly introduced to you previously. Suppose we want to know whether $G$ with $|V(G)| = n$ vertices has a clique of size $\ge k$, but we only know how to solve Large Clique.

If by chance $n = 2k$, then this is already the Large Clique problem. If $n < 2k$, then we form a new graph $G'$ by adding $2k-n$ new isolated vertices to $G$. It's obvious that $G'$ has a $k$-clique iff $G$ does, and furthermore $|V(G')| = 2k$ so this can be determined by Large Clique.

Finally, if $n > 2k$ then we instead form $G'$ by adjoining $n-2k$ fully-connected vertices to $G$. Since $k + (n-2k) = n-k$, $G'$ has an $(n-k)$-clique iff $G$ has a $k$-clique. Since $|V(G')| = 2n-2k$, this is again equivalent to Large Clique.

For a more complete solution, you should also verify that $G'$ is only polynomially larger than $G$.

The same easy idea can be used to establish the “$r|V|$” variant previously mentioned, with not much more work (it takes a bit more care to figure out exactly how many vertices to add).

-