Algorithmic trade-offs for girth approximation in undirected graphs

We present several new efficient algorithms for approximating the girth, g, of weighted and unweighted n -vertex, m -edge undirected graphs. For undirected graphs with polynomially bounded, integer, non-negative edge weights, we provide an algorithm that for every integer k ≥ 1, runs in Õ ( m + n 1 + 1/ k log g ) time and returns a cycle of length at most 2 kg. For unweighted, undirected graphs we present an algorithm that for every k ≥ 1, runs in Õ ( n 1 + 1/ k ) time and returns a cycle of length at most 2 k [ g /2], an almost k -approximation. Both algorithms provide trade-offs between the running time and the quality of the approximation. We also obtain faster algorithms for approximation factors better than 2, and improved approximations when the girth is odd or small (e. g. , 3 and 4).

Authors

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

Keywords

No keywords are indexed for this paper.