2026-07-22T17:54:06Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20180 2024-07-02T07:52:50Z ddc:004 open_access

Fast Approximate Counting of Cycles Censor-Hillel, Keren Even, Tomer Vassilevska Williams, Virginia Approximate triangle counting Approximate cycle counting Fast matrix multiplication Fast rectangular matrix multiplication 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Keren Censor-Hillel and Tomer Even and Virginia Vassilevska Williams 2024 Is Part Of LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2024.37 urn:nbn:de:0030-drops-201809 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.37 eng https://creativecommons.org/licenses/by/4.0/legalcode