{"ID":5551663,"CreatedAt":"2026-07-02T01:54:51.863792489Z","UpdatedAt":"2026-07-04T13:37:00.247962456Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.00938","arxiv_id":"2607.00938","title":"Tighter bounds for weighted and unweighted shortest cycle approximation","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.","short_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 i...","url_abs":"https://arxiv.org/abs/2607.00938","url_pdf":"https://arxiv.org/pdf/2607.00938v1","authors":"[\"Avi Kadria\",\"Liam Roditty\",\"Virginia Vassilevska Williams\"]","published":"2026-07-01T13:40:42Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}