Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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

2 Answers 2

up vote 2 down vote accepted

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$."

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.