Fast Approximate Counting of Cycles

Mina Dalirrooyfard, Surya Mathialagan, Virginia Vassilevska WilliamsarXiv 2023 · DOI · arXiv

Abstract

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±ε)-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.
BibTeX
@misc{dalirrooyfard2023fast,
  author = {Mina Dalirrooyfard and Surya Mathialagan and Virginia Vassilevska Williams},
  title = {{Fast Approximate Counting of Cycles}},
  year = {2023},
  eprint = {2307.15871},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2307.15871},
}
Figure