Global vs. s-t Vertex Connectivity Beyond Sequential: Almost-Perfect Reductions & Near-Optimal Separations
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913759739510784 |
|---|---|
| author | Blikstad, Joakim Jiang, Yonggang Mukhopadhyay, Sagnik Yingchareonthawornchai, Sorrachai |
| author_facet | Blikstad, Joakim Jiang, Yonggang Mukhopadhyay, Sagnik Yingchareonthawornchai, Sorrachai |
| contents | A recent breakthrough by [LNPSY STOC'21] showed that solving s-t vertex connectivity is sufficient (up to polylogarithmic factors) to solve (global) vertex connectivity in the sequential model. This raises a natural question: What is the relationship between s-t and global vertex connectivity in other computational models? In this paper, we demonstrate that the connection between global and s-t variants behaves very differently across computational models:
1.In parallel and distributed models, we obtain almost tight reductions from global to s-t vertex connectivity. In PRAM, this leads to a $n^{ω+o(1)}$-work and $n^{o(1)}$-depth algorithm for vertex connectivity, improving over the 35-year-old $\tilde O(n^{ω+1})$-work $O(\log^2n)$-depth algorithm by [LLW FOCS'86], where $ω$ is the matrix multiplication exponent and $n$ is the number of vertices. In CONGEST, the reduction implies the first sublinear-round (when the diameter is moderately small) vertex connectivity algorithm. This answers an open question in [JM STOC'23].
2. In contrast, we show that global vertex connectivity is strictly harder than s-t vertex connectivity in the two-party communication setting, requiring $\tilde Θ(n^{1.5})$ bits of communication. The s-t variant was known to be solvable in $\tilde O(n)$ communication [BvdBEMN FOCS'22]. Our results resolve open problems raised by [MN STOC'20, BvdBEMN FOCS'22, AS SOSA'23].
At the heart of our results is a new graph decomposition framework we call \emph{common-neighborhood clustering}, which can be applied in multiple models. Finally, we observe that global vertex connectivity cannot be solved without using s-t vertex connectivity, by proving an s-t to global reduction in dense graphs, in the PRAM and communication models. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_20366 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Global vs. s-t Vertex Connectivity Beyond Sequential: Almost-Perfect Reductions & Near-Optimal Separations Blikstad, Joakim Jiang, Yonggang Mukhopadhyay, Sagnik Yingchareonthawornchai, Sorrachai Data Structures and Algorithms A recent breakthrough by [LNPSY STOC'21] showed that solving s-t vertex connectivity is sufficient (up to polylogarithmic factors) to solve (global) vertex connectivity in the sequential model. This raises a natural question: What is the relationship between s-t and global vertex connectivity in other computational models? In this paper, we demonstrate that the connection between global and s-t variants behaves very differently across computational models: 1.In parallel and distributed models, we obtain almost tight reductions from global to s-t vertex connectivity. In PRAM, this leads to a $n^{ω+o(1)}$-work and $n^{o(1)}$-depth algorithm for vertex connectivity, improving over the 35-year-old $\tilde O(n^{ω+1})$-work $O(\log^2n)$-depth algorithm by [LLW FOCS'86], where $ω$ is the matrix multiplication exponent and $n$ is the number of vertices. In CONGEST, the reduction implies the first sublinear-round (when the diameter is moderately small) vertex connectivity algorithm. This answers an open question in [JM STOC'23]. 2. In contrast, we show that global vertex connectivity is strictly harder than s-t vertex connectivity in the two-party communication setting, requiring $\tilde Θ(n^{1.5})$ bits of communication. The s-t variant was known to be solvable in $\tilde O(n)$ communication [BvdBEMN FOCS'22]. Our results resolve open problems raised by [MN STOC'20, BvdBEMN FOCS'22, AS SOSA'23]. At the heart of our results is a new graph decomposition framework we call \emph{common-neighborhood clustering}, which can be applied in multiple models. Finally, we observe that global vertex connectivity cannot be solved without using s-t vertex connectivity, by proving an s-t to global reduction in dense graphs, in the PRAM and communication models. |
| title | Global vs. s-t Vertex Connectivity Beyond Sequential: Almost-Perfect Reductions & Near-Optimal Separations |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2503.20366 |