The Complexity of Distributed Minimum Weight Cycle Approximation
Summary
No summary yet. VIRAT can read this paper and write a plain-language summary of its aim, methods, key findings and limitations.
Summarise with VIRAT Free to try with your Science Catalogs account.Abstract
We study the Minimum Weight Cycle (MWC) problem in the $\mathsf{CONGEST}$ model of distributed computing. For undirected weighted graphs, we give a randomized $(k+1)$-approximation algorithm for every \underline{real number} $k \geq (1+\sqrt{5})/2 \approx 1.618$. The algorithm runs in \[ \tilde{O}\left(n^{\frac{k+1}{2k+1}} + D\right) \] rounds, where $n$ is the number of nodes and $D$ is the unweighted diameter of the graph. Varying $k$ therefore yields a smooth trade-off between approximation ratio and round complexity. On the lower-bound side, assuming the Erdős girth conjecture, we prove that for every \underline{integer} $k \geq 1$ and every $ε> 0$, any randomized $(k+1-ε)$-approximation algorithm for MWC requires \[ \tildeΩ\left(n^{\frac{k+1}{2k+1}}+D\right) \] rounds. The lower bound holds for both directed unweighted graphs and undirected weighted graphs, even on graphs of diameter $Θ(\log n)$. Consequently, for every integer $k \geq 2$, our upper and lower bounds for undirected weighted graphs match up to polylogarithmic factors. This gives a nearly tight characterization of the round complexity of approximate MWC across an infinite family of approximation ratios. These results improve the previous state of the art of Manoharan and Ramachandran (PODC 2024), who gave a $(2+ε)$-approximation algorithm for undirected weighted graphs in $\tilde{O}(n^{2/3}+D)$ rounds, and proved an $\tildeΩ(\sqrt{n})$ lower bound for arbitrary approximation ratios in directed unweighted and undirected weighted graphs.
Fields of Study & Subjects
Complexity and Algorithms in Graphs
Advanced Graph Theory Research
Graph Theory and Algorithms
Publication details
- Journal / source
- arXiv (Cornell University)
- Publication date
- 26 March 2026
- Language
- EN
- Document type
- Preprint