Total: 1
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ℓ⌈g2⌉−2⌊ε⌈g2⌉⌋, 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⌈g2⌉−2⌊ε⌈g2⌉⌋ in ˜O(n1+12−ε) time. Kadria \etal{} presented also an algorithm that finds a cycle of length at most 2ℓ⌈g2⌉ 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ℓ(⌊g−12⌋)−2(⌊ε⌊g−12⌋⌋+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. [...]