Parallel and Distributed Expander Decomposition: Simple, Fast, and Near-Optimal
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912177255874560 |
|---|---|
| author | Chen, Daoyuan Meierhans, Simon Gutenberg, Maximilian Probst Saranurak, Thatchaphol |
| author_facet | Chen, Daoyuan Meierhans, Simon Gutenberg, Maximilian Probst Saranurak, Thatchaphol |
| contents | Expander decompositions have become one of the central frameworks in the design of fast algorithms. For an undirected graph $G=(V,E)$, a near-optimal $ϕ$-expander decomposition is a partition $V_1, V_2, \ldots, V_k$ of the vertex set $V$ where each subgraph $G[V_i]$ is a $ϕ$-expander, and only an $\widetilde{O}(ϕ)$-fraction of the edges cross between partition sets.
In this article, we give the first near-optimal parallel algorithm to compute $ϕ$-expander decompositions in near-linear work $\widetilde{O}(m/ϕ^2)$ and near-constant span $\widetilde{O}(1/ϕ^4)$. Our algorithm is very simple and likely practical. Our algorithm can also be implemented in the distributed Congest model in $\tilde{O}(1/ϕ^4)$ rounds.
Our results surpass the theoretical guarantees of the current state-of-the-art parallel algorithms [Chang-Saranurak PODC'19, Chang-Saranurak FOCS'20], while being the first to ensure that only an $\tilde{O}(ϕ)$ fraction of edges cross between partition sets. In contrast, previous algorithms [Chang-Saranurak PODC'19, Chang-Saranurak FOCS'20] admit at least an $O(ϕ^{1/3})$ fraction of crossing edges, a polynomial loss in quality inherent to their random-walk-based techniques. Our algorithm, instead, leverages flow-based techniques and extends the popular sequential algorithm presented in [Saranurak-Wang SODA'19]. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_13451 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Parallel and Distributed Expander Decomposition: Simple, Fast, and Near-Optimal Chen, Daoyuan Meierhans, Simon Gutenberg, Maximilian Probst Saranurak, Thatchaphol Data Structures and Algorithms Expander decompositions have become one of the central frameworks in the design of fast algorithms. For an undirected graph $G=(V,E)$, a near-optimal $ϕ$-expander decomposition is a partition $V_1, V_2, \ldots, V_k$ of the vertex set $V$ where each subgraph $G[V_i]$ is a $ϕ$-expander, and only an $\widetilde{O}(ϕ)$-fraction of the edges cross between partition sets. In this article, we give the first near-optimal parallel algorithm to compute $ϕ$-expander decompositions in near-linear work $\widetilde{O}(m/ϕ^2)$ and near-constant span $\widetilde{O}(1/ϕ^4)$. Our algorithm is very simple and likely practical. Our algorithm can also be implemented in the distributed Congest model in $\tilde{O}(1/ϕ^4)$ rounds. Our results surpass the theoretical guarantees of the current state-of-the-art parallel algorithms [Chang-Saranurak PODC'19, Chang-Saranurak FOCS'20], while being the first to ensure that only an $\tilde{O}(ϕ)$ fraction of edges cross between partition sets. In contrast, previous algorithms [Chang-Saranurak PODC'19, Chang-Saranurak FOCS'20] admit at least an $O(ϕ^{1/3})$ fraction of crossing edges, a polynomial loss in quality inherent to their random-walk-based techniques. Our algorithm, instead, leverages flow-based techniques and extends the popular sequential algorithm presented in [Saranurak-Wang SODA'19]. |
| title | Parallel and Distributed Expander Decomposition: Simple, Fast, and Near-Optimal |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2410.13451 |