Faster sublinear approximations of $k$-cliques for low arboricity graphs

Talya Eden, Dana Ron, C. Seshadhri

Given query access to an undirected graph $G$, we consider the problem of computing a $(1\pm \epsilon )$-approximation of the number of $k$-cliques in $G$. The standard query model for gene…