Improved girth approximation in weighted undirected graphs

Avi Kadria, Liam Roditty, Aaron Sidford, Virginia Vassilevska Williams, Uri Zwick · 2025

Read Improved girth approximation in weighted undirected graphs by Avi Kadria, Liam Roditty, Aaron Sidford, Virginia Vassilevska Williams, Uri Zwick (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-13869.txt.

Introduction

Avi Kadria and co-authors tackle a classic graph problem in this 2025 paper. The girth of a graph is the length of its shortest cycle. Finding a near-shortest cycle fast is hard when edges carry weights. The team gives an algorithm that works for any weighted undirected graph.

For a chosen trade-off setting, the method finds a cycle no more than about four-thirds times that setting times the true girth. It runs in time close to the best known for the simpler unweighted case. The result beats the earlier best method for weighted graphs on both speed and accuracy. Such algorithms matter for network design and for routing problems.

Catalog record

CREATORAvi Kadria, Liam Roditty, Aaron Sidford, Virginia Vassilevska Williams, Uri Zwick
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE56 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-13869

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Improved girth approximation in weighted undirected graphs Avi Kadria, Liam Roditty, Aaron Sidford, Virginia Vassilevska Williams, Uri Zwick Abstract Let G = ( V , E , ℓ ) G=(V,E,\ell) be a n n -node m m -edge weighted undirected graph, where ℓ : E → ( 0 , ∞ ) \ell:E\rightarrow(0,\infty) is a real length function defined on its edges, and let g g denote the girth of G G , i.e., the length of its shortest cycle. We present an algorithm that, for any input, integer k ≥ 1 k\geq 1 , in O ⁡ ( k ​ n 1 + 1 / k ​ log ⁡ n + m ⁡ ( k + log ⁡ n ) ) O(kn^{1+1/k}\log{n}+m(k+\log{n})) expected time finds a cycle of length at most 4 ​ k 3 ​ g \frac{4k}{3}g . This algorithm nearly matches a O ⁡ ( n 1 + 1 / k ​ log ⁡ n ) O(n^{1+1/k}\log{n}) -time algorithm of [ KRS+22 ] which applied to unweighted graphs of girth 3 3 . For weighted graphs, this result also improves upon the previous state-of-the-art algorithm that in O ⁡ ( ( n 1 + 1 / k ​ log ⁡ n + m ) ​ log ⁡ ( n ​ M ) ) O((n^{1+1/k}\log n+m)\log(nM)) time, where ℓ : E → [ 1 , M ] \ell:E\rightarrow[1,M] is an integral length function, finds a cycle of length at most 2 ​ k ​ g 2kg [ KRS+22 ] . For k = 1 k=1 this result improves upon the result of Roditty and Tov [ RT13 ] . 1 Introduction The length of a shortest cycle, known as the girth of the graph, is a key parameter often used to shed light on the structure of graph theory problems (e.g., [ LW97 , OPT01 , HW16 ] ). Correspondingly, the problem of computing a shortest cycle in an undirected graph is fundamental in algorithmic graph theory and has been studied extensively for decades (e.g., [ IR78 , AYZ97 , YZ97 , LL09 , Duc21 ] and more). Prominent special cases, e.g., detecting triangles in graphs, are foundational to algorithm design and complexity theory and are useful in practice as well (e.g., [ EK10 , Chapter 3] ). Given the prominence of shortest cycle and girth computation problems, extensive effort has gone into developing fast algorithms for them. The best known runtime for computing the girth of an n -vertex, m -edge unweighted graph is O(\min\{n^{\omega},mn\}) f [ IR78 ] , where \omega<2.373 is the matrix multiplication exponent. For graphs with nonnegative integer edge lengths bounded by M , the best known runtime is \tilde{O}(\min\{Mn^{\omega},mn\}) 1 1 1 \tilde{O}(f(n)) denotes O(f(n)\textrm{poly}\log(n)) . [ RV11 ] . For arbitrary edge lengths and no negative cycles, the fastest algorithms solve All-PPairs Shortest Paths (APSP), whose fastest running time to date is O(\min\{mn+n^{2}\log\log n,n^{3}/\exp(\sqrt{\log n})\}) [ Pet04 , Wil18 ] . Improving upon these bounds significantly would constitute a major breakthrough in algorithm design and fine grained complexity; [ VW18 , LVW18 ] clarified this hardness and proved that such improvements would contradict the APSP hardness hypothesis 2 2 2 The APSP hypothesis states that no O(n^{3-\varepsilon}) algorithm exists for computing APSP in a general weighted graph . Given the above hardness for exact girth computation, it is natural to ask which trade-offs between running times and approximation ratios are possible. For unweighted graphs, where all edge lengths are 1 , there has been extensive work on this question, and there are a variety of results depending on the graph’s girth and the desired approximation [ LL09 , RT13 , RV12 , DKS17 , KRS+22 ] . Perhaps most relevant to this paper, Kadria et al. [ KRS+22 ] presented a collection of new algorithms for girth approximation, including an algorithm that for any input unweighted n -vertex undirected graph of girth g and an integer parameter k\geq 1 finds a cycle of length at most 2k\cdot\lceil g/2\rceil in O(n^{1+1/k}\log n) time. This result improved upon a result of Dahlgaard, Knudsen, and Stöckel [ DKS17 ] that provided an algorithm which in the same running time of O(n^{1+1/k}\log n) finds a cycle of length at most 2^{k}g , for k\geq 2 , w.h.p. Less is known for the weighted problem of approximating the girth of n -vertex m -edge undirected graphs with edge lengths in the range [1,M] and girth g . Until recently, the state-of-the-art running time for this problem included a result of Roditty and Tov [ RT13 ] which obtained an \tilde{O}(n^{2}\log M) -time 4/3 -approximation algorithm which improved upon a 2 -approximation algorithm of Lingas and Lundell [ LL09 ] , as well as a result of Ducoffe [ Duc21 ] which obtained an O(m+n^{5/3}{\rm polylog}M) -time 2 -approximation algorithm. Unlike in the case of unweighted graphs, no general trade-off between running time and approximation quality was known. Kadria et al. [ KRS+22 ] obtained the first running time versus approximation tradeoff for weighted girth computation. They presented an algorithm that for any integer k\geq 1 finds a cycle of length at most 2k\cdot g in O((n^{1+1/k}\log n+m)\log(nM)) time. For k=1 , this result offers a worse trade-off than both Roditty and Tov [ RT13 ] and Ducoffe [ Duc21 ] . Additionally, the approximation quality achieved by this result is almost twice as large as that achievable for unweighted graphs with a comparable running time. In light of these results, the central question we ask in this paper is: Is it possible to design a single algorithm that yields improved runtime versus approximation quality trade-offs for undirected weighted graphs? Our main result is the following theorem: Theorem 1 (Improved girth approximation) . Let G=(V,E,\ell) be a weighted, undirected graph, where \ell:E\rightarrow(0,\infty) . Let g be the unknown girth of G . For every integer k\geq 1 3 3 3 Throughout the paper, we assume that k\leq\log{n} since further increasing k no longer reduces the running time , there is an algorithm whose expected running time is O(kn^{1+1/k}\log{n}+m\log{n}) that finds a cycle C such that \ell(C)\leq\frac{4k}{3}g . Among the tools we use to prove the theorem include: approximate distance oracles [ TZ05 ] , Spira’s single-source shortest paths algorithm [ Spi73 ] , a problem related to 2-dimensional orthogonal range reporting from computational geometry, and an extension of ideas from Kadria et al. [ KRS+22 ] . Our result (up to logarithmic factors in running time) strictly improves upon Kadria et al. [ KRS+22 ] , computing a (\frac{4k}{3}g) -approximation (rather than 2kg ) in a comparable running time. Furthermore, the approximation quality versus runtime trade-off matches that of Roditty and Tov [ RT13 ] for k=1 . We note that improving beyond the approximation factor of 4/3 approximation of Roditty and Tov [ RT13 ] in the same running time faces a barrier: any (4/3-\varepsilon) -approximation algorithm for \varepsilon>0 would be able to detect whether a graph contains a triangle, and via [ VW18 ] , we know that triangle detection is closely related to BMM. Thus, obtaining a quadratic time combinatorial (4/3-\varepsilon) -approximation algorithm would contradict the BMM Hypothesis [ VW18 ] . Moreover, our tradeoff

Read the complete text