Near Optimal Bounds for Replacement Paths and Related Problems in the CONGEST Model
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916252831711232 |
|---|---|
| author | Manoharan, Vignesh Ramachandran, Vijaya |
| author_facet | Manoharan, Vignesh Ramachandran, Vijaya |
| contents | We present several results in the CONGEST model on round complexity for Replacement Paths (RPaths), Minimum Weight Cycle (MWC), and All Nodes Shortest Cycles (ANSC). We study these fundamental problems in both directed and undirected graphs, both weighted and unweighted. Many of our results are optimal to within a polylog factor: For an $n$-node graph $G$ we establish near linear lower and upper bounds for computing RPaths if $G$ is directed and weighted, and for computing MWC and ANSC if $G$ is weighted, directed or undirected; near $\sqrt{n}$ lower and upper bounds for undirected weighted RPaths; and $Θ(D)$ bound for undirected unweighted RPaths. We also present lower and upper bounds for approximation versions of these problems, notably a $(2-(1/g))$-approximation algorithm for undirected unweighted MWC that runs in $\tilde{O}(\sqrt{n}+D)$ rounds, improving on the previous best bound of $\tilde{O}(\sqrt{ng}+D)$ rounds, where $g$ is the MWC length. We present a $(1+ε)$-approximation algorithm for directed weighted RPaths, which beats the linear lower bound for exact RPaths. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2205_14797 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Near Optimal Bounds for Replacement Paths and Related Problems in the CONGEST Model Manoharan, Vignesh Ramachandran, Vijaya Data Structures and Algorithms Distributed, Parallel, and Cluster Computing We present several results in the CONGEST model on round complexity for Replacement Paths (RPaths), Minimum Weight Cycle (MWC), and All Nodes Shortest Cycles (ANSC). We study these fundamental problems in both directed and undirected graphs, both weighted and unweighted. Many of our results are optimal to within a polylog factor: For an $n$-node graph $G$ we establish near linear lower and upper bounds for computing RPaths if $G$ is directed and weighted, and for computing MWC and ANSC if $G$ is weighted, directed or undirected; near $\sqrt{n}$ lower and upper bounds for undirected weighted RPaths; and $Θ(D)$ bound for undirected unweighted RPaths. We also present lower and upper bounds for approximation versions of these problems, notably a $(2-(1/g))$-approximation algorithm for undirected unweighted MWC that runs in $\tilde{O}(\sqrt{n}+D)$ rounds, improving on the previous best bound of $\tilde{O}(\sqrt{ng}+D)$ rounds, where $g$ is the MWC length. We present a $(1+ε)$-approximation algorithm for directed weighted RPaths, which beats the linear lower bound for exact RPaths. |
| title | Near Optimal Bounds for Replacement Paths and Related Problems in the CONGEST Model |
| topic | Data Structures and Algorithms Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2205.14797 |