Parallel Small Vertex Connectivity in Near-Linear Work and Polylogarithmic Depth
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912316461678592 |
|---|---|
| author | Jiang, Yonggang Yun, Changki |
| author_facet | Jiang, Yonggang Yun, Changki |
| contents | We present a randomized parallel algorithm in the {\sf PRAM} model for $k$-vertex connectivity. Given an undirected simple graph, our algorithm either finds a set of fewer than $k$ vertices whose removal disconnects the graph or reports that no such set exists. The algorithm runs in $O(m \cdot \text{poly}(k, \log n))$ work and $O(\text{poly}(k, \log n))$ depth, which is nearly optimal for any $k = \text{poly}(\log n)$. Prior to our work, algorithms with near-linear work and polylogarithmic depth were known only for $k=3$ [Miller, Ramachandran, STOC'87]; for $k=4$, sequential algorithms achieving near-linear time were known [Forster, Nanongkai, Yang, Saranurak, Yingchareonthawornchai, SODA'20], but no algorithm with near-linear work could achieve even sublinear (on $n$) depth. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_06033 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Parallel Small Vertex Connectivity in Near-Linear Work and Polylogarithmic Depth Jiang, Yonggang Yun, Changki Data Structures and Algorithms We present a randomized parallel algorithm in the {\sf PRAM} model for $k$-vertex connectivity. Given an undirected simple graph, our algorithm either finds a set of fewer than $k$ vertices whose removal disconnects the graph or reports that no such set exists. The algorithm runs in $O(m \cdot \text{poly}(k, \log n))$ work and $O(\text{poly}(k, \log n))$ depth, which is nearly optimal for any $k = \text{poly}(\log n)$. Prior to our work, algorithms with near-linear work and polylogarithmic depth were known only for $k=3$ [Miller, Ramachandran, STOC'87]; for $k=4$, sequential algorithms achieving near-linear time were known [Forster, Nanongkai, Yang, Saranurak, Yingchareonthawornchai, SODA'20], but no algorithm with near-linear work could achieve even sublinear (on $n$) depth. |
| title | Parallel Small Vertex Connectivity in Near-Linear Work and Polylogarithmic Depth |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2504.06033 |