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 $\epsilon > 0$, any randomized $(k+1-\epsilon)$-approximation algorithm for MWC requires \[ \tilde{\Omega}\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 $\Theta(\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+\epsilon)$-approximation algorithm for undirected weighted graphs in $\tilde{O}(n^{2/3}+D)$ rounds, and proved an $\tilde{\Omega}(\sqrt{n})$ lower bound for arbitrary approximation ratios in directed unweighted and undirected weighted graphs.
From: Yi-Jun Chang [view email]
[v1]
Thu, 26 Mar 2026 12:17:32 UTC (63 KB)
[v2]
Fri, 27 Mar 2026 02:11:08 UTC (63 KB)
[v3]
Thu, 16 Jul 2026 03:32:29 UTC (60 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。