Fast Approximate Counting of Cycles

We consider the problem of approximate counting of triangles and longer fixed length cycles in directed graphs. For triangles, Tětek [ICALP’22] gave an algorithm that returns a $(1\pm \text{eps})$-approximation in $\tilde{O}(n^{\omega }\mathrm{/}{t}^{\omega -2})$ time, where $t$ is the unknown number of triangles in the given $n$ node graph and $\omega <2.372$ is the matrix multiplication exponent. We obtain an improved algorithm whose running time is, within polylogarithmic factors the same as that for multiplying an $n\times n\mathrm{/}t$ matrix by an $n\mathrm{/}t\times n$ matrix. We then extend our framework to obtain the first nontrivial $(1\pm \text{eps})$-approximation algorithms for the number of $h$-cycles in a graph, for any constant $h\ge 3$. Our running time is $$\tilde{O}(\mathsf{M}\mathsf{M}(n,n\mathrm{/}{t}^{1\mathrm{/}(h-2)},n)),\text{the time to multiply }n\times \frac{n}{t^{1\mathrm{/}(h-2)}}\text{ by }\frac{n}{t^{1\mathrm{/}(h-2)}}\times n\text{ matrices}\mathrm{.}$$ Finally, we show that under popular fine-grained hypotheses, this running time is optimal.