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.

  • $\begingroup$ Did you mean sub exponential? $\endgroup$ – R B Apr 19 '15 at 5:06
  • $\begingroup$ 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. $\endgroup$ – Ram Apr 19 '15 at 5:16
  • $\begingroup$ 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. $\endgroup$ – R B Apr 19 '15 at 9:54
  • 1
    $\begingroup$ So I assume you allow exponential time, as long as the query complexity is sublinear, right? $\endgroup$ – Igor Shinkar Apr 20 '15 at 14:31
  • 1
    $\begingroup$ @IgorShinkar Yes, I allow exponential running time as long as my query complexity is sublinear. $\endgroup$ – 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.