Approximating the Girth of an Undirected, Weighted Graph for Larger Approximation Factors
In the authors' words
The girth of a weighted undirected graph is defined as the length of a shortest cycle in the graph. In this paper, we give a randomized algorithm to approximate the girth of a graph with vertices and edges to within a factor of for any real . We assume that all edge weights are non-negative. For sufficiently high approximation factors, our algorithm outperforms the state of the art by polylogarithmic factors. Specifically, for approximation factors where , our algorithm gives a runtime of , while instantiating the previous best -approximation algorithms with yields a running time of (Kadria, Roditty, and Vassilevska Williams, arXiv:2607.00938). Furthermore, the algorithm presented here is conceptually simple, has relatively small constants, eschews single-source shortest path and sparse spanner algorithms, and employs a new technique, which we call "random filtering." That being said, the basic algorithm returns only a numerical estimate for the girth, rather than a witness cycle.
Appeared: Monday, October 19. arXiv. Preprint, not yet peer-reviewed.