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, could it be the right approach?
On
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).
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$."