# 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)$?

• $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? Dec 16, 2012 at 0:29
• @RealzSlaw $n\choose k$ is polynomial
– M.M
Jul 8, 2015 at 17:04
• @M.M Yea I think you are right. Jul 8, 2015 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, ($$k$$ being a constant with respect to $$n$$.) 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).
• I don't really get it. If a graph has a clique of size $k$, it has a clique of size $k-1$, a clique of size $k-2$ and so on. So asking if a graph has a clique of size at least $k$ ($k$ or bigger) it's equivalent to ask if it has a clique of size $k$ (without even considering if such clique is maximal or not). Dec 18, 2020 at 0:05