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?
Best Answer
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$."