Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2512.00176 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912737849769984 |
|---|---|
| author | Quanrud, Kent |
| author_facet | Quanrud, Kent |
| contents | We present randomized algorithms that compute $(1+ε)$-approximate minimum global edge and vertex cuts in weighted directed graphs in $O(\log^4(n) / ε)$ and $O(\log^5(n)/ε)$ single-commodity flows, respectively. With the almost-linear time flow algorithm of [CKL+22], this gives almost linear time approximation schemes for edge and vertex connectivity. By setting $ε$ appropriately, this also gives faster exact algorithms for small vertex connectivity.
At the heart of these algorithms is a divide-and-conquer technique called "shrink-wrapping" for a certain well-conditioned rooted Steiner connectivity problem. Loosely speaking, for a root $r$ and a set of terminals, shrink-wrapping uses flow to certify the connectivity from a root $r$ to some of the terminals, and for the remaining uncertified terminals, generates an $r$-cut where the sink component both (a) contains the sink component of the minimum $(r,t)$-cut for each uncertified terminal $t$ and (b) has size proportional to the number of uncertified terminals. This yields a divide-and-conquer scheme over the terminals where we can divide the set of terminals and compute their respective minimum $r$-cuts in smaller, contracted subgraphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_00176 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Approximating Directed Connectivity in Almost-Linear Time Quanrud, Kent Data Structures and Algorithms We present randomized algorithms that compute $(1+ε)$-approximate minimum global edge and vertex cuts in weighted directed graphs in $O(\log^4(n) / ε)$ and $O(\log^5(n)/ε)$ single-commodity flows, respectively. With the almost-linear time flow algorithm of [CKL+22], this gives almost linear time approximation schemes for edge and vertex connectivity. By setting $ε$ appropriately, this also gives faster exact algorithms for small vertex connectivity. At the heart of these algorithms is a divide-and-conquer technique called "shrink-wrapping" for a certain well-conditioned rooted Steiner connectivity problem. Loosely speaking, for a root $r$ and a set of terminals, shrink-wrapping uses flow to certify the connectivity from a root $r$ to some of the terminals, and for the remaining uncertified terminals, generates an $r$-cut where the sink component both (a) contains the sink component of the minimum $(r,t)$-cut for each uncertified terminal $t$ and (b) has size proportional to the number of uncertified terminals. This yields a divide-and-conquer scheme over the terminals where we can divide the set of terminals and compute their respective minimum $r$-cuts in smaller, contracted subgraphs. |
| title | Approximating Directed Connectivity in Almost-Linear Time |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2512.00176 |