What is the best known approximation for the computational complexity of the clique problem? Is it accurate to consider it $O(2^n)$?
$\begingroup$
$\endgroup$
3
-
1$\begingroup$ What is a complexity approximation? $\endgroup$Yuval Filmus– Yuval Filmus2012-12-03 00:18:46 +00:00Commented Dec 3, 2012 at 0:18
-
$\begingroup$ big Oh notation for an algorithm. Examples include O(n^2), O(nlogn) etc. $\endgroup$loveToCode– loveToCode2012-12-03 00:23:08 +00:00Commented Dec 3, 2012 at 0:23
-
$\begingroup$ I rephrased the question to ask what you seem to be asking, but with standard terminology. $\endgroup$Raphael– Raphael2012-12-03 07:57:58 +00:00Commented Dec 3, 2012 at 7:57
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
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.
-
$\begingroup$ does not have the answer $\endgroup$loveToCode– loveToCode2012-12-03 01:56:38 +00:00Commented Dec 3, 2012 at 1:56
-
1$\begingroup$ @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). $\endgroup$Luke Mathieson– Luke Mathieson2012-12-03 02:23:14 +00:00Commented Dec 3, 2012 at 2:23
-
1$\begingroup$ 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). $\endgroup$Raphael– Raphael2012-12-03 08:07:04 +00:00Commented Dec 3, 2012 at 8:07