Tell me more ×
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.
up vote 0 down vote favorite

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

share|improve this question
1  
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

1 Answer

up vote 4 down vote accepted

Wikipedia is usually a good starting reference to well-known problems as the clique. There is a list of the fastest known algorithms for CLIQUE including references.

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.

share|improve this answer
does not have the answer – loveToCode Dec 3 '12 at 1:56
1  
@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
1  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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