arXiv preprint ·
Deterministic Girth Approximation in Weighted Undirected Graphs
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We give deterministic algorithms for approximating the girth~$g$ of an undirected graph with $n$ vertices, $m$ edges, and nonnegative real edge lengths. For every integer $k\geq2$, our algorithm returns a cycle of length at most $\frac{2k}{3}g$ in $O((m+n^{1+2/k})k\log n)$ worst-case time. For every constant~$k$, this matches the stretch and the expected running time of the randomized algorithms of Kadria, Roditty, Sidford, Vassilevska Williams, and Zwick [SODA'23, SICOMP'26] and Kadria, Roditty, and Vassilevska Williams [ESA'26]. In general, it loses only a factor of $O(\min\{k,\log n\})$ in the term that depends on~$m$. The best previous deterministic trade-off, of Kadria, Roditty, Sidford, Vassilevska Williams, and Zwick [SODA'22], has stretch~$k$ instead of $\frac{2k}{3}$ at the same exponent (for even~$k$) and requires integer edge lengths. In particular, for $k=3$ we obtain a deterministic $2$-approximation in $O((m+n^{5/3})\log n)$ time for real edge lengths, whereas the deterministic algorithm of Ducoffe [SIDMA'21] for real lengths has stretch $2+\varepsilon$. Our main technical idea is that a deterministic construction of the Thorup--Zwick hierarchy used by these algorithms may stop exploring as soon as it finds a cycle: the approximation analysis only needs clusters truncated at half the best cycle certificate found, so balls stopped in this way need not be hit. Together with a degree-weighted selection rule, this bounds the work of each level by its number of edges and stored ball entries. More generally, a ball need not be hit whenever the analysis only uses clusters up to a radius bounded by a certificate that the algorithm has already found.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Improved classical optimization of fermionic Hamiltonians beyond Gaussian states
Faster Deterministic Approximation for Counting Knapsack
Conditional Indexing Lower Bounds and Normalization Boundaries for Elastic Subsequence Matching
The Matching Number Characterizes the Query Complexity of Edge Counting and Degree Moment Estimation
Subset Sum and Integer Programming Feasibility Test in Near-Optimal Time
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.