3
$\begingroup$

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?

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

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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