2026-07-22T01:28:55Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22720 2026-04-17T05:32:45Z ddc:004 open_access

Listing 6-Cycles in Sparse Graphs Vassilevska Williams, Virginia Westover, Alek Graph algorithms cycles listing fine-grained complexity sparse graphs This work considers the problem of output-sensitive listing of occurrences of 2k-cycles for fixed constant k ≥ 2 in an undirected host graph with m edges and t 2k-cycles. Recent work of Jin and Xu (and independently Abboud, Khoury, Leibowitz, and Safier) [STOC 2023] gives an O(m^{4/3}+t) time algorithm for listing 4-cycles, and recent work by Jin, Vassilevska Williams and Zhou [SOSA 2024] gives an Õ(n²+t) time algorithm for listing 6-cycles in n node graphs. We focus on resolving the next natural question: obtaining listing algorithms for 6-cycles in the sparse setting, i.e., in terms of m rather than n. Previously, the best known result here is the better of Jin, Vassilevska Williams and Zhou’s Õ(n²+t) algorithm and Alon, Yuster and Zwick’s O(m^{5/3}+t) algorithm. We give an algorithm for listing 6-cycles with running time Õ(m^{1.6}+t). Our algorithm is a natural extension of Dahlgaard, Knudsen and Stöckel’s [STOC 2017] algorithm for detecting a 2k-cycle. Our main technical contribution is the analysis of the algorithm which involves a type of "supersaturation" lemma relating the number of 2k-cycles in a bipartite graph to the sizes of the parts in the bipartition and the number of edges. We also give a simplified analysis of Dahlgaard, Knudsen and Stöckel’s 2k-cycle detection algorithm (with a small polylogarithmic increase in the running time), which is helpful in analyzing our listing algorithm. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Virginia Vassilevska Williams and Alek Westover 2025 Is Part Of LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2025.92 urn:nbn:de:0030-drops-227207 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.92 eng https://creativecommons.org/licenses/by/4.0/legalcode