2026/07/01 by Avi Kadria, Liam Roditty, Virginia Vassilevska Williams
#cs.DS
We study the problem of approximating the length of a shortest cycle in a given graph, known as the girth of the graph. The state-of-the-art approximation algorithms for unweighted graphs by Kadria et al. [SODA'22] and Roditty and Trabelsi [arXiv'25] achieve the following trade-off: for every integer k≥ 2, there is an O(n1+2/k) time algorithm that achieves a (2k/3)-approximation for the girth in unweighted n-node graphs. The first result of this paper is to achieve the same trade-off for m-edge, n-node graphs with non-negative real edge weights: a 2k/3-approximation algorithm running in O(m+n1+2/k) time. The dependence on m is unavoidable in weighted graphs. Our result improves on the work of Kadria et al.~[SODA'23] and Ducoffe [ICALP'19 and SIDMA'21], who were only able to achieve such a trade-off for some values of k. We also prove new fine-grained lower bounds for girth approximation and related problems in unweighted graphs.