6
$\begingroup$

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.

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

1 Answer 1

5
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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