9
$\begingroup$

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

Improve this question
$\endgroup$
3
  • $\begingroup$ $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? $\endgroup$
    – Realz Slaw
    Dec 16, 2012 at 0:29
  • $\begingroup$ @RealzSlaw $n\choose k$ is polynomial $\endgroup$
    – M.M
    Jul 8, 2015 at 17:04
  • $\begingroup$ @M.M Yea I think you are right. $\endgroup$
    – Realz Slaw
    Jul 8, 2015 at 17:51

1 Answer 1

Reset to default
15
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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). $\endgroup$
    – ABu
    Dec 18, 2020 at 0:05

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