# Computational complexity of the clique problem

What is the best known approximation for the computational complexity of the clique problem? Is it accurate to consider it $O(2^n)$?

• What is a complexity approximation? – Yuval Filmus Dec 3 '12 at 0:18
• big Oh notation for an algorithm. Examples include O(n^2), O(nlogn) etc. – loveToCode Dec 3 '12 at 0:23
• I rephrased the question to ask what you seem to be asking, but with standard terminology. – Raphael Dec 3 '12 at 7:57

Apparently, the fastest algorithm we know runs in time $O(1.1888^n)$, so that's the best upper bound on the complexity of CLIQUE we have. As for lower bounds, we don't have a super-polynomial one, or otherwise P=NP? would have been solved.
• @loveToCode, the Wikipedia article has the asymptotic running time for a large variety of algorithms for CLIQUE and its common variants, if the answer you're after isn't there, could you perhaps refine your question to be more precise as to what you're asking. The answer to the question you seem to have asked it definitely there, it's $O(1.888^{n})$ (Robson, 2001). – Luke Mathieson Dec 3 '12 at 2:23
• I edited the answer to be a bit more informative. Note that I tried to find a peer reviewed version of the tech report giving the $O(1.888^n)$ algorithm but was not successful. Therefore, you might be interested in Exact Algorithms for NP-Hard Problems: A Survey (free download via Google Scholar) by G.J. Woeginger (2003). – Raphael Dec 3 '12 at 8:07