# What are the best known upper bounds and lower bounds for computing O(log n)-Clique?

Input: a graph with n nodes, Output: A clique of size $O(\log n)$, Providing links to references would be great

• please fix the title (lon -> log) – Suresh Venkat Aug 26 '10 at 4:13

The best known upper bound is essentially $n^{O(\log n)}$. You can improve a little on the constant factor in the big-O using fast matrix multiplication, but that's about it. There are a lot of algorithmic references on the $k$-clique problem which describe this reduction, it originates from papers of Itai and Rodeh and Nesetril and Poljak. (Apologies to Czech readers, I am ignorant of the proper diacritical marks.) See http://en.wikipedia.org/wiki/Clique_problem

If you could solve $\log n$-clique in $n^{\varepsilon \log n}$ for every $\varepsilon > 0$, then you could also solve 3SAT in subexponential time. This can be seen as a "lower bound" to further progress. One way to prove this is to first show that if $\log n$-clique in $n^{\varepsilon \log n}$ for every $\varepsilon > 0$, then MaxCut on $n$ nodes is in $2^{\varepsilon n}$ time for every $\varepsilon > 0$. This follows directly from a theorem in my ICALP'04 paper that relates the time complexity of MaxCut to the time complexity of $k$-clique. From there, one can appeal to standard reductions to reduce 3SAT to MaxCut, showing that subexponential MaxCut implies subexponential 3SAT.

In terms of unconditional lower bounds, nothing nontrivial is known, to my knowledge. We don't even know how to show that $O(\log n)$-clique isn't solvable with an algorithm that runs in linear time and uses only logarithmic workspace.

• \eps isn't standard latex. although it's at least somewhat readable :) – Suresh Venkat Aug 26 '10 at 6:06
• so I noticed... :) – Ryan Williams Aug 26 '10 at 6:07
• @RyanWilliams I know this is an old answer, but I was wondering if you know whether these results apply when we restrict to random graphs. e.g. is there an algorithm that runs in time $O(n^{\epsilon \log n})$ that finds a clique of size $(1+\epsilon)$ for $G(n,1/2)$ with high probability? – mm8511 Dec 4 '17 at 17:53

An earlier observation in the same vein as Williams' is given in "Limited vs. Polynomial Nondeterminism" by Feige and Kilian in The Chicago Journal of Theoretical Computer Science (1997)

A (not unconditional) lower bound comes from the clique problem being complete for the parameterized complexity class W1. That is, we do not expect to be able to find a clique of size $k$ in $f(k)n^c$. So there is good reason to believe that the trivial upper bound may not be significantly improved.

• Even more strongly, Chen et al. showed that we are unlikely to find a clique of size k in $f(k)n^{o(k)}$ time, unless there is a subexponential algorithm for every problem in SNP. So the k parameter seems to be a lower bound on the degree of the polynomial. dx.doi.org/10.1016/j.jcss.2006.04.007 – András Salamon Sep 13 '10 at 12:41

As I understand it this problem is interesting even for random graphs (in the Erdős–Rényi model in which all graphs are equally likely): we know that the maximum clique size is $(2+o(1))\log_2 n$, but the biggest cliques we can find in polynomial time (e.g. by finding any maximal clique) have size only $(1+o(1))\log_2 n$. See e.g. the introduction of Alon, Krivelevich, and Sudakov, "Finding a large hidden clique in a random graph", SODA 1998, where they credit these observations to a 1976 paper of Karp and conjecture that no polynomial algorithm can do better than $(1+o(1))\log_2 n$.