Tighter bounds for weighted and unweighted shortest cycle approximation
2026-07-01 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors study how to find a shortest cycle in a graph, which is called the girth. Previous algorithms worked well for unweighted graphs, but this paper extends those results to graphs with weights on the edges, keeping the same balance between accuracy and speed. Their method runs efficiently depending on both the number of edges and nodes, improving on earlier work that only managed this for certain cases. They also establish new fundamental limits on how well you can approximate the girth in unweighted graphs.
girthgraph theoryapproximation algorithmweighted graphsunweighted graphstime complexityfine-grained complexityshortest cycle
Authors
Avi Kadria, Liam Roditty, Virginia Vassilevska Williams
Abstract
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\geq 2$, there is an $\tilde{O}(n^{1+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 $\tilde{O}(m+n^{1+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.