2026-08-16T20:55:32Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19398 2024-03-06T11:03:56Z ddc:004 open_access

Listing 4-Cycles Abboud, Amir Khoury, Seri Leibowitz, Oree Safier, Ron Graph algorithms cycles listing subgraph detection fine-grained complexity We study the fine-grained complexity of listing all 4-cycles in a graph on n nodes, m edges, and t such 4-cycles. The main result is an Õ(min(n²,m^{4/3})+t) upper bound, which is best-possible up to log factors unless the long-standing O(min(n²,m^{4/3})) upper bound for detecting a 4-cycle can be broken. Moreover, it almost-matches recent 3-SUM-based lower bounds for the problem by Abboud, Bringmann, and Fischer (STOC 2023) and independently by Jin and Xu (STOC 2023). Notably, our result separates 4-cycle listing from the closely related triangle listing for which higher conditional lower bounds exist, and rule out such a "detection plus t" bound. We also show by simple arguments that our bound cannot be extended to mild generalizations of the problem such as reporting all pairs of nodes that participate in a 4-cycle. [Independent work: Jin and Xu [Ce Jin and Yinzhan Xu, 2023] also present an algorithm with the same time bound.] Schloss Dagstuhl – Leibniz-Zentrum für Informatik Amir Abboud and Seri Khoury and Oree Leibowitz and Ron Safier 2023 Is Part Of LIPIcs, Volume 284, 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2023.25 urn:nbn:de:0030-drops-193985 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2023.25 eng https://creativecommons.org/licenses/by/4.0/legalcode