You can find a $k$-clique in $n^k$ time by examining all possible sets of vertices of size $k$. So why is it NP-complete to determine if there is a clique of size greater than $k$? It looks like you can solve it in polynomial time if $k$ is a constant.
Asked
Active
Viewed 1,712 times
2 Answers
2
Indeed we could resolve the $k$-clique problem for fixed $k$ by inspecting $\binom{n}{k}$ subgraphs. However, the number $k$ is considered an input to the problem too.
In the $k$-clique problem, the input is an undirected graph and a number $k$, and the output is a clique of size $k$ if one exists (or, sometimes, all cliques of size $k$). -- Wikipedia
If e.g. $k=\lfloor n/2 \rfloor$, then $\binom{n}{k}$ increases exponentially (not polynomially) with the input size.
Rebecca J. Stones
- 26,845
-
Oh you're right, $k$ can be really big. Thanks! – Jessica Feb 12 '14 at 03:27
-1
I think finding a k-clique is simply O(m+n). If we know k, we can store a list of all the nodes which have a degree of atleast k-1. Then for every node in that list, we check if all of its neighbors or atleast n-1 of its neighbors (depending on whether degree of the node is n-1 or > n-1) have degree n-1 or not. Using adjacency lists, this step takes O(m+n). So total complexity is O(m+n). It's linear.
