%ACensor-Hillel, Keren%AEven, Tomer%AVassilevska_Williams, Virginia%ABringmann, Karl Ed.%AGrohe, Martin Ed.%APuppis, Gabriele Ed.%ASvensson, Ola Ed.%D2024%ISchloss Dagstuhl – Leibniz-Zentrum für Informatik
%KApproximate triangle counting; Approximate cycle counting Fast matrix multiplication; Fast rectangular matrix multiplication; Mathematics of computing → Approximation algorithms; Mathematics of computing → Graph algorithms
%MOSTI ID: 10524467
%PMedium: X; Size: 20 pages; 1118518 bytes; Other: application/pdf
%TFast Approximate Counting of Cycles
%XWe 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±ε)-approximation in Õ(n^ω/t^{ω-2}) time, where t is the unknown number of triangles in the given n node graph and ω < 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× n/t matrix by an n/t × n matrix. We then extend our framework to obtain the first nontrivial (1± ε)-approximation algorithms for the number of h-cycles in a graph, for any constant h ≥ 3. Our running time is Õ(MM(n,n/t^{1/(h-2)},n)), the time to multiply n × n/(t^{1/(h-2)}) by n/(t^{1/(h-2)) × n matrices.
Finally, we show that under popular fine-grained hypotheses, this running time is optimal.