Enregistré dans:
| Auteurs principaux: | , , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2603.25368 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911547214790656 |
|---|---|
| author | Chang, Yi-Jun Chen, Yanyu Dey, Dipan Jiang, Yonggang Mishra, Gopinath Nguyen, Hung Thuan Yang, Mingyang |
| author_facet | Chang, Yi-Jun Chen, Yanyu Dey, Dipan Jiang, Yonggang Mishra, Gopinath Nguyen, Hung Thuan Yang, Mingyang |
| contents | We investigate the \emph{minimum weight cycle (MWC)} problem in the $\mathsf{CONGEST}$ model of distributed computing.
For undirected weighted graphs, we design a randomized algorithm that achieves a $(k+1)$-approximation, for any \emph{real} number $k \ge 1$. The round complexity of algorithm is \[ \tilde{O}\!\Big( n^{\frac{k+1}{2k+1}} + n^{\frac{1}{k}} + D\, n^{\frac{1}{2(2k+1)}} + D^{\frac{2}{5}} n^{\frac{2}{5}+\frac{1}{2(2k+1)}} \Big). \] where $n$ denotes the number of nodes and $D$ is the unweighted diameter of the graph. This result yields a smooth trade-off between approximation ratio and round complexity. In particular, when $k \geq 2$ and $D = \tilde{O}(n^{1/4})$, the bound simplifies to \[ \tilde{O}\!\left(
n^{\frac{k+1}{2k+1}} \right) \]
On the lower bound side, assuming the Erdős girth conjecture, we prove that for every \emph{integer} $k \ge 1$, any randomized $(k+1-ε)$-approximation algorithm for MWC requires \[ \tildeΩ\!\left(
n^{\frac{k+1}{2k+1}} \right) \] rounds. This lower bound holds for both directed unweighted and undirected weighted graphs, and applies even to graphs with small diameter $D = Θ(\log n)$.
Taken together, our upper and lower bounds \emph{match up to polylogarithmic factors} for graphs of sufficiently small diameter $D = \tilde{O}(n^{1/4})$ (when $k \geq 2$), yielding a nearly tight bound on the distributed complexity of the problem.
Our results improve upon the previous state of the art: Manoharan and Ramachandran (PODC~2024) demonstrated a $(2+ε)$-approximation algorithm for undirected weighted graphs with round complexity $\tilde{O}(n^{2/3}+D)$, and proved that for any arbitrarily large number $α$, any $α$-approximation algorithm for directed unweighted or undirected weighted graphs requires $Ω(\sqrt{n}/\log n)$ rounds. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_25368 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | The Complexity of Distributed Minimum Weight Cycle Approximation Chang, Yi-Jun Chen, Yanyu Dey, Dipan Jiang, Yonggang Mishra, Gopinath Nguyen, Hung Thuan Yang, Mingyang Distributed, Parallel, and Cluster Computing We investigate the \emph{minimum weight cycle (MWC)} problem in the $\mathsf{CONGEST}$ model of distributed computing. For undirected weighted graphs, we design a randomized algorithm that achieves a $(k+1)$-approximation, for any \emph{real} number $k \ge 1$. The round complexity of algorithm is \[ \tilde{O}\!\Big( n^{\frac{k+1}{2k+1}} + n^{\frac{1}{k}} + D\, n^{\frac{1}{2(2k+1)}} + D^{\frac{2}{5}} n^{\frac{2}{5}+\frac{1}{2(2k+1)}} \Big). \] where $n$ denotes the number of nodes and $D$ is the unweighted diameter of the graph. This result yields a smooth trade-off between approximation ratio and round complexity. In particular, when $k \geq 2$ and $D = \tilde{O}(n^{1/4})$, the bound simplifies to \[ \tilde{O}\!\left( n^{\frac{k+1}{2k+1}} \right) \] On the lower bound side, assuming the Erdős girth conjecture, we prove that for every \emph{integer} $k \ge 1$, any randomized $(k+1-ε)$-approximation algorithm for MWC requires \[ \tildeΩ\!\left( n^{\frac{k+1}{2k+1}} \right) \] rounds. This lower bound holds for both directed unweighted and undirected weighted graphs, and applies even to graphs with small diameter $D = Θ(\log n)$. Taken together, our upper and lower bounds \emph{match up to polylogarithmic factors} for graphs of sufficiently small diameter $D = \tilde{O}(n^{1/4})$ (when $k \geq 2$), yielding a nearly tight bound on the distributed complexity of the problem. Our results improve upon the previous state of the art: Manoharan and Ramachandran (PODC~2024) demonstrated a $(2+ε)$-approximation algorithm for undirected weighted graphs with round complexity $\tilde{O}(n^{2/3}+D)$, and proved that for any arbitrarily large number $α$, any $α$-approximation algorithm for directed unweighted or undirected weighted graphs requires $Ω(\sqrt{n}/\log n)$ rounds. |
| title | The Complexity of Distributed Minimum Weight Cycle Approximation |
| topic | Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2603.25368 |