<p>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&lt;\frac12$, but your question asks for a parameterization that remains sublinear for all $\rho$ and all $\epsilon&gt;0$.</p>

CC BY-SA 3.0
2015-12-06T21:16:56.370Z
2015-12-06T21:16:56.370Z
David Eppstein
<p>Let $G=(V,E)$ be a graph. For a given $\rho \leq |V|$ and $\epsilon$ with $(0&lt;\epsilon&lt;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)$. </p>

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

<p>Thanks in advance. </p>

CC BY-SA 3.0
2015-04-19T05:06:15.863Z
Did you mean *sub exponential*?
R B
CC BY-SA 3.0
2015-04-19T05:16:45.430Z
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
CC BY-SA 3.0
2015-04-19T09:54:47.450Z
This seems **highly** unlikely. Currently, we have no $n^{o(k)}$ algorithm for deciding $k$-clique, and as this problem $W[1]$-hard w.r.t. $k$, there is no much hope for it either.
R B
CC BY-SA 3.0
2015-04-20T14:31:45.103Z
So I assume you allow exponential time, as long as the query complexity is sublinear, right?
Igor Shinkar
CC BY-SA 3.0
2015-04-20T21:19:46.740Z
By $f(1/\epsilon, 1/\delta,o(n^2))$, do you actually mean $f(\epsilon, \delta) \cdot o(n^2)$ ?
daniello
CC BY-SA 3.0
2015-04-21T03:23:31.077Z
@IgorShinkar Yes, I allow exponential running time as long as my query complexity is sublinear.
Ram
CC BY-SA 3.0
2015-04-21T03:24:22.833Z
@daniello Yes. Sorry for the confusion.
Ram
CC BY-SA 3.0
2015-04-21T21:08:30.667Z
one more question: Do you allow adaptivity?
Igor Shinkar
CC BY-SA 3.0
2015-04-22T04:36:17.800Z
@IgorShinkar, Thanks for your interest. Sure if adaptivity can give us something nontrivial.
Ram
<graph-theory><graph-algorithms><approximation-algorithms>
Approximating the clique size of the graph
Ram
# Approximating the clique size of the graph

(Asked by: username_0 on 2015-04-19)

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).$

Thanks in advance.

**Tags:** graph-theory, graph-algorithms, approximation-algorithms

> **Comments:**
> **username_1**: Did you mean *sub exponential*?  
> **username_0**: 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.  
> **username_1**: This seems **highly** unlikely. Currently, we have no $n^{o(k)}$ algorithm for deciding $k$-clique, and as this problem $W[1]$-hard w.r.t. $k$, there is no much hope for it either.  
> **username_2**: So I assume you allow exponential time, as long as the query complexity is sublinear, right?  
> **username_3**: By $f(1/\epsilon, 1/\delta,o(n^2))$, do you actually mean $f(\epsilon, \delta) \cdot o(n^2)$ ?  
> **username_0**: @IgorShinkar Yes, I allow exponential running time as long as my query complexity is sublinear.  
> **username_0**: @username_3 Yes. Sorry for the confusion.  
> **username_2**: one more question: Do you allow adaptivity?  
> **username_0**: @IgorShinkar, Thanks for your interest. Sure if adaptivity can give us something nontrivial.  

---

## 1 answers

### Answer by username_4 on 2015-12-06. Score: 5

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$.


---

