# Approximating the Girth of an Undirected, Weighted Graph for Larger Approximation Factors

Preprint · Eliyahu Yablon

- Archive id: arxiv:2610.23698
- Published: 2026-10-16
- arXiv: https://arxiv.org/abs/2610.23698
- Citations: 0
- Source URL: https://arxiv.org/abs/2610.23698
- PDF: https://arxiv.org/pdf/2610.23698
- Provenance: arxiv

## Abstract

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 $O\\left(m^{1+2/(k-1)} n^{1/(k-1)}\\right)$ algorithm to approximate the girth of a graph with $n$ vertices and $m$ edges to within a factor of $k$ for any real $k$. 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 $k = c\\frac{\\log n}{\\log \\log n}$ where $c\>5$, our algorithm gives a runtime of $O\\left(m (\\log n)^{5/c}\\right)$, while instantiating the previous best $k$-approximation algorithms with $k = c\\frac{\\log n}{\\log \\log n}$ yields a running time of $O\\left( \\frac{cn (\\log n)^{2 + 4/(3c)} }{\\log \\log n} + m\\log n\\right)$ (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.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

Topics: [Algorithms & Complexity Breakthroughs](https://space-kitty.com/topics/algorithms-complexity)

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.