Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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

share|improve this question

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

    
$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

1 Answer 1

up vote 6 down vote accepted

To elaborate on the comments, there are different problems being considered here.

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

share|improve this answer
    
Perhaps you should mention why it s NP Hard. You didnt answer the question –  AJed Dec 16 '12 at 5:24
    
@AJed - true, I'll add that in for completeness. –  usul Dec 16 '12 at 6:37

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