The Taub Faculty of Computer Science Events and Talks

We present a sublinear-time algorithm for approximating the number of $k$-cliques in an input graph.

We assume the standard general graphs access model via (1) degree queries, (2) neighbor queries and (3) pair queries.

Consider a graph with $n$ vertices, $m$ edges, and $k$-cliques. We design an algorithm that outputs a $(1+\eps)$-approximation (with high probability) for $k$ with expected query complexity and running time $O\left(\frac{n}{\clk^{1/k}}+\frac{m^{k/2}}{\clk} \right)\poly(\log n, 1/\eps,k)$.

Furthermore, we prove a lower bound showing that our algorithm is essentially optimal (up to the dependence on $\log n$, $1/\eps$ and $k$).