# Why is the clique problem NP-complete? [duplicate]

Possible Duplicate:
Is the k-clique problem NP-complete?

I've been lately reading about the clique problem, specifically, the variety of the clique problem of deciding whether a given graph $G$ with $n$ nodes has a clique of at least size $k$.

Why is this problem $NP$-complete? Could one solve this problem in polynomial time by trying out each possible group of $k$ nodes in the graph and checking if this group is a clique?

Wouldn't this algorithm run in time $O(\binom{n}{k})$ or $O(\frac{n!}{(n-k)!k!})$ or $O(n^2)$?

-

## marked as duplicate by Juho, AJed, Realz Slaw, Merbs, A.SchulzDec 16 '12 at 8:35

$O(\binom{n}{k})$ is not polynomial time, is it? Is $O(\frac{n!}{(n-k)!k!})$? $O(n^2)$ is, but how do you propose solving it in $O(n^2)$ time? – Realz Slaw Dec 16 '12 at 0:29
@RealzSlaw $n\choose k$ is polynomial – M.M Jul 8 '15 at 17:04
@M.M Yea I think you are right. – Realz Slaw Jul 8 '15 at 17:51

The 3-clique problem is, given a graph, does it have a clique of size 3? This is solvable in polynomial time. Likewise, for any fixed $k$, the $k$-clique problem (given a graph, is there a clique of size $k$) is solvable in polynomial time.

But in the clique problem, we are given both the graph and $k$ and asked if there is a clique larger than size $k$. This problem is NP-Complete. For example, let's suppose someone sets $k = \frac{n}{2}$. Then the running time you give is definitely exponential.

This should make intuitive sense -- in the $k$-clique problem, if I fix $k$ to be, say 1000, then as graphs get really really large (like trillions of nodes), I still only have to check every set of 1000 nodes. But in the clique problem, as the graph gets really gigantic, the sets I have to check might get gigantic too.

(Edit. To finish answering the question, clique is NP-hard because for example 3SAT can be reduced to it in polynomial time, and clique is in NP. However, $k$-Clique (for any given $k$) is not NP-hard).

-