Deterministic Vertex Connectivity via Common-Neighborhood Clustering and Pseudorandomness
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_ | 1866916663492870144 |
|---|---|
| author | Jiang, Yonggang Nalam, Chaitanya Saranurak, Thatchaphol Yingchareonthawornchai, Sorrachai |
| author_facet | Jiang, Yonggang Nalam, Chaitanya Saranurak, Thatchaphol Yingchareonthawornchai, Sorrachai |
| contents | We give a deterministic algorithm for computing a global minimum vertex cut in a vertex-weighted graph $n$ vertices and $m$ edges in $\widehat O(mn)$ time. This breaks the long-standing $\widehat Ω(n^{4})$-time barrier in dense graphs, achievable by trivially computing all-pairs maximum flows. Up to subpolynomial factors, we match the fastest randomized $\tilde O(mn)$-time algorithm by [Henzinger, Rao, and Gabow'00], and affirmatively answer the question by [Gabow'06] whether deterministic $O(mn)$-time algorithms exist even for unweighted graphs. Our algorithm works in directed graphs, too.
In unweighted undirected graphs, we present a faster deterministic $\widehat O(mκ)$-time algorithm where $κ\le n$ is the size of the global minimum vertex cut. For a moderate value of $κ$, this strictly improves upon all previous deterministic algorithms in unweighted graphs with running time $\widehat
O(m(n+κ^{2}))$ [Even'75], $\widehat O(m(n+κ\sqrt{n}))$ [Gabow'06], and $\widehat O(m2^{O(κ^{2})})$ [Saranurak and Yingchareonthawornchai'22]. Recently, a linear-time algorithm has been shown by [Korhonen'24] for very small $κ$.
Our approach applies the common-neighborhood clustering, recently introduced by [Blikstad, Jiang, Mukhopadhyay, Yingchareonthawornchai'25], in novel ways, e.g., on top of weighted graphs and on top of vertex-expander decomposition. We also exploit pseudorandom objects often used in computational complexity communities, including crossing families based on dispersers from [Wigderson and Zuckerman'99; TaShma, Umans and Zuckerman'01] and selectors based on linear lossless condensers [Guruswwami, Umans and Vadhan'09; Cheraghchi'11]. To our knowledge, this is the first application of selectors in graph algorithms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_20985 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Deterministic Vertex Connectivity via Common-Neighborhood Clustering and Pseudorandomness Jiang, Yonggang Nalam, Chaitanya Saranurak, Thatchaphol Yingchareonthawornchai, Sorrachai Data Structures and Algorithms We give a deterministic algorithm for computing a global minimum vertex cut in a vertex-weighted graph $n$ vertices and $m$ edges in $\widehat O(mn)$ time. This breaks the long-standing $\widehat Ω(n^{4})$-time barrier in dense graphs, achievable by trivially computing all-pairs maximum flows. Up to subpolynomial factors, we match the fastest randomized $\tilde O(mn)$-time algorithm by [Henzinger, Rao, and Gabow'00], and affirmatively answer the question by [Gabow'06] whether deterministic $O(mn)$-time algorithms exist even for unweighted graphs. Our algorithm works in directed graphs, too. In unweighted undirected graphs, we present a faster deterministic $\widehat O(mκ)$-time algorithm where $κ\le n$ is the size of the global minimum vertex cut. For a moderate value of $κ$, this strictly improves upon all previous deterministic algorithms in unweighted graphs with running time $\widehat O(m(n+κ^{2}))$ [Even'75], $\widehat O(m(n+κ\sqrt{n}))$ [Gabow'06], and $\widehat O(m2^{O(κ^{2})})$ [Saranurak and Yingchareonthawornchai'22]. Recently, a linear-time algorithm has been shown by [Korhonen'24] for very small $κ$. Our approach applies the common-neighborhood clustering, recently introduced by [Blikstad, Jiang, Mukhopadhyay, Yingchareonthawornchai'25], in novel ways, e.g., on top of weighted graphs and on top of vertex-expander decomposition. We also exploit pseudorandom objects often used in computational complexity communities, including crossing families based on dispersers from [Wigderson and Zuckerman'99; TaShma, Umans and Zuckerman'01] and selectors based on linear lossless condensers [Guruswwami, Umans and Vadhan'09; Cheraghchi'11]. To our knowledge, this is the first application of selectors in graph algorithms. |
| title | Deterministic Vertex Connectivity via Common-Neighborhood Clustering and Pseudorandomness |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2503.20985 |