Fast Approximate Counting of Cycles
Lists
Only you see this
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},
}