<p>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)</p>

CC BY-SA 2.5
2010-08-28T08:46:16.653Z
and here's a link to the paper: http://cjtcs.cs.uchicago.edu/articles/1997/1/contents.html
Suresh Venkat
CC BY-SA 2.5
2010-08-29T05:10:28.820Z
Thanks Andreas, I had forgotten about this one... they show that if $O(\log n)$-clique is in polynomial time then you get subexponential algorithms for $NP$.
Ryan Williams
CC BY-SA 2.5
2010-08-28T08:08:02.560Z
2010-08-28T08:08:02.560Z
Andreas Björklund
<p>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.</p>

CC BY-SA 2.5
2010-09-13T12:41:26.383Z
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.
http://dx.doi.org/10.1016/j.jcss.2006.04.007
András Salamon
CC BY-SA 2.5
2010-08-28T20:22:46.213Z
2010-09-13T12:22:34.270Z
2010-09-13T12:22:34.270Z
Lev Reyzin
<p>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", <a href="http://portal.acm.org/citation.cfm?id=314613.315014" rel="nofollow">SODA 1998</a>, 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$.</p>

CC BY-SA 2.5
2010-08-28T18:20:35.697Z
2010-08-29T05:49:35.170Z
2010-08-29T05:49:35.170Z
David Eppstein
<p>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 <a href="http://en.wikipedia.org/wiki/Clique_problem">http://en.wikipedia.org/wiki/Clique_problem</a></p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2017-12-04T17:53:07.027Z
@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
CC BY-SA 2.5
2010-08-26T06:06:53.957Z
\eps isn't standard latex. although it's at least somewhat readable :)
Suresh Venkat
CC BY-SA 2.5
2010-08-26T06:07:49.853Z
so I noticed... :)
Ryan Williams
CC BY-SA 2.5
2010-08-26T06:02:57.387Z
2010-08-26T06:02:57.387Z
Ryan Williams
<p>Input: a graph with n nodes,
Output: A clique of size $O(\log n)$,
Providing links to references would be great</p>

CC BY-SA 2.5
2010-08-26T04:13:54.093Z
please fix the title (lon -> log)
Suresh Venkat
<ds.algorithms><reference-request><graph-theory><lower-bounds><upper-bounds>
What are the best known upper bounds and lower bounds for computing O(log n)-Clique?
Mohammad Al-Turkistany
# What are the best known upper bounds and lower bounds for computing O(log n)-Clique?

(Asked by: username_0 on 2010-08-26)

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

**Tags:** ds.algorithms, reference-request, graph-theory, lower-bounds, upper-bounds
> **Comments:**
> **username_1**: please fix the title (lon -> log)  

---

## 4 answers

### Answer by username_3 on 2010-08-26. Score: 15 | Accepted answer

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.

> **Comments:**
> **username_1**: \eps isn't standard latex. although it's at least somewhat readable :)  
> **username_3**: so I noticed... :)  
> **username_7**: @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?  

---

### Answer by username_2 on 2010-08-28. Score: 8

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)

> **Comments:**
> **username_1**: and here's a link to the paper: http://cjtcs.cs.uchicago.edu/articles/1997/1/contents.html  
> **username_3**: Thanks Andreas, I had forgotten about this one... they show that if $O(\log n)$-clique is in polynomial time then you get subexponential algorithms for $NP$.  

---

### Answer by username_4 on 2010-08-28. Score: 7

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.

> **Comments:**
> **username_5**: 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. http://dx.doi.org/10.1016/j.jcss.2006.04.007  

---

### Answer by username_6 on 2010-08-28. Score: 5

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](http://portal.acm.org/citation.cfm?id=314613.315014), 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$.


---

