# Approximating the clique size of the graph

Let $G=(V,E)$ be a graph. For a given $\rho \leq |V|$ and $\epsilon$ with $(0<\epsilon<1)$, is there any sublinear query algorithm known/possible to decide if the graph has a clique of size $\rho$, or all the cliques are of size at most $\rho(1-\epsilon)$.

More precisely, for a given probability tolerance $\delta$ and error tolerance $\epsilon$, algorithm queries $f(\frac{1}{\epsilon}, \frac{1}{\delta}).o(n^2)$ many position of the corresponding adjacency matrix of the graph, and accept with probability at least $1-\delta$ if the graph has a clique of size $\rho$, or reject probability at least $1-\delta$ if all the cliques are of size at most $\rho(1-\epsilon).$

• Did you mean sub exponential?
– R B
Apr 19 '15 at 5:06
• Sorry for the confusion. I meant that algorithm looks only at a small portion of the graph, and could decide with high probability that whether the graph has a clique large size, or all cliques are very small.
– Ram
Apr 19 '15 at 5:16
• This seems highly unlikely. Currently, we have no $n^{o(k)}$ algorithm for deciding $k$-clique, and as this problem $W$-hard w.r.t. $k$, there is no much hope for it either.
– R B
Apr 19 '15 at 9:54
• So I assume you allow exponential time, as long as the query complexity is sublinear, right? Apr 20 '15 at 14:31
• @IgorShinkar Yes, I allow exponential running time as long as my query complexity is sublinear.
– Ram
Apr 21 '15 at 3:23

It's not possible. The reason is that, to distinguish an $n$-vertex graph with no edges (clique size 1) from a graph with a single randomly-chosen edge (clique size 2) requires $\Theta(n^2)$ queries. So it's not possible to get sublinear queries for $\rho=2$ and $\epsilon<\frac12$, but your question asks for a parameterization that remains sublinear for all $\rho$ and all $\epsilon>0$.