Approximate Triangle Counting via Sampling and Fast Matrix Multiplication

There is a simple O(n^3/eps^2 T) time algorithm for 1+-eps-approximate triangle counting where T is the number of triangles in the graph and n the number of vertices. At the same time, one may count triangles exactly using fast matrix multiplication in time O(n^\omega). Is it possible to get a negative dependency on the number of triangles T while retaining the state-of-the-art n^\omega dependency on n? We answer this question positively by providing an algorithm which runs in time O(n^\omega/T^(\omega - 2)) poly(n^o(1)/eps). This is optimal in the sense that as long as the exponent of T is independent of n, T, it cannot be improved while retaining the dependency on n. Our algorithm improves upon the state of the art when T >> 1 and T << n. We also consider approximate triangle counting in sparse graphs.

The paper is a (shared) best student paper at ICALP 2022.