2025/07/18 by Avi Kadria, Liam Roditty, Kadria, Avi +7
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.2507.13869
openalex publication_date 2025/07/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let G = (V,E,ℓ) be a n-node m-edge weighted undirected graph, where ℓ: E → (0,∞) is a real length function defined on its edges, and let g denote the girth of G, i.e., the length of its shortest cycle. We present an algorithm that, for any input, integer k ≥ 1, in O(kn1+1/klogn + m(k+logn)) expected time finds a cycle of length at most (4k)/(3)g. This algorithm nearly matches a O(n1+1/klogn)-time algorithm of \citeKadriaRSWZ22 which applied to unweighted graphs of girth 3. For weighted graphs, this result also improves upon the previous state-of-the-art algorithm that in O((n1+1/klog n+m)log (nM)) time, where ℓ: E → [1, M] is an integral length function, finds a cycle of length at most 2kg~\citeKadriaRSWZ22. For k=1 this result improves upon the result of Roditty and Tov~\citeRodittyT13.