2025/07/02 by Roditty, Liam, Trabelsi, Plia
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2507.02061
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 O(ℓ ⋅ n1 + (1)/(ℓ - ε)) that returns a cycle of length at most 2ℓ \lceil (g)/(2) \rceil - 2 \lfloor ε \lceil (g)/(2) \rceil \rfloor, where ℓ ≥ 2 is an integer and ε ∈ [0,1], for every graph with g = polylog(n). Our algorithm generalizes an algorithm of Kadria \etal [SODA'22] that computes a cycle of length at most 4\lceil (g)/(2) \rceil - 2\lfloor ε \lceil (g)/(2) \rceil \rfloor in O(n1 + (1)/(2 - ε)) time. Kadria \etal presented also an algorithm that finds a cycle of length at most 2ℓ \lceil (g)/(2) \rceil in O(n1 + (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 O(ℓ⋅ m1+1/(ℓ-ε)) time randomized algorithm that returns a cycle of length at most 2ℓ(\lfloor (g-1)/(2)\rfloor) - 2(\lfloor ε \lfloor (g-1)/(2)\rfloor \rfloor+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. [...]