Improved girth approximation in weighted undirected graphs

Let G = ( V, E, ℓ) be a n -nodes m -edges weighted undirected graph, where ℓ: E → (0, ∞) is a real length function defined on its edges. Let g be the length of the shortest cycle in G. We present an algorithm that in O ( kn 1+1/ k log n + m(k + log n )) expected running time finds a cycle of length at most, for every integer k ≥ 1. This improves upon the previous best algorithm that in O((n 1+1/k log n + m ) log( nM )) time, where ℓ: E → [1, M ] is an integral length function, finds a cycle of length at most 2 kg [KRS + 22]. For k = 1 our algorithm also improves the result of Roditty and Tov [RT13].

Authors

• Avi Kadria
• Liam Roditty
• Aaron Sidford
• Virginia Vassilevska Williams
• Uri Zwick

Keywords

No keywords are indexed for this paper.