2026-10-01T07:51:44Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26074 2026-09-23T23:59:38Z ddc:004 open_access

New Algorithms for Girth and Cycle Detection Roditty, Liam Trabelsi, Plia Graph algorithms All pairs shortest path Girth Cycle approximation Let G = (V,E) be an unweighted undirected graph with n vertices and m edges. Let g be the girth of G, that is, the length of a shortest cycle in G. We present a randomized algorithm with a running time of Õ(𝓁 ⋅ n^{1 + 1/(𝓁-ε)}) that returns a cycle of length at most 2𝓁 ⌈g/2⌉ - 2 ⌊ε⌈g/2⌉⌋, where 𝓁 ≥ 2 is an integer and ε ∈ [0,1], for every graph with g = polylog(n). Our algorithm generalizes an algorithm of Kadria et al. [SODA'22] that computes a cycle of length at most 4 ⌈g/2⌉ - 2 ⌊ε⌈g/2⌉⌋ in Õ(n^{1 + 1/(2 - ε)}) time. Kadria et al. presented also an algorithm that finds a cycle of length at most 2𝓁 ⌈g/2⌉ in Õ(n^{1 + 1/(𝓁)}) time, where 𝓁 must be an integer. Our algorithm generalizes this algorithm, as well, by replacing the integer parameter 𝓁 in the running time exponent with a real-valued parameter 𝓁 - ε, thereby offering greater flexibility in parameter selection and enabling a broader spectrum of combinations between running times and cycle lengths. We also show that for sparse graphs a better tradeoff is possible, by presenting an Õ(𝓁⋅ m^{1+ 1/(𝓁-ε)}) time randomized algorithm that returns a cycle of length at most 2𝓁(⌊(g-1)/2⌋) - 2(⌊ε⌊(g-1)/2⌋⌋+1), where 𝓁 ≥ 3 is an integer and ε ∈ [0,1), for every graph with g = polylog(n). To obtain our algorithms we develop several techniques and introduce a formal definition of hybrid cycle detection algorithms. Both may prove useful in broader contexts, including other cycle detection and approximation problems. Among our techniques is a new cycle searching technique, in which we search for a cycle from a given vertex and possibly all its neighbors in linear time. Using this technique together with more ideas we develop two hybrid algorithms. The first allows us to obtain an Õ(m^{2-2/(⌈g/2⌉+1))-time, (+1)-approximation of g. The second is used to obtain our Õ(𝓁⋅ n^{1+ 1/(𝓁-ε)})-time and Õ(𝓁⋅ m^{1+ 1/(𝓁-ε)})-time approximation algorithms. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Liam Roditty and Plia Trabelsi 2026 Is Part Of LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2026.38 urn:nbn:de:0030-drops-260742 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.38 eng https://creativecommons.org/licenses/by/4.0/legalcode