# Approximating Directed Connectivity in Almost-Linear Time

Preprint · Kent Quanrud

- Archive id: arxiv:2512.00176
- Published: 2025-11-28
- arXiv: https://arxiv.org/abs/2512.00176
- Source URL: https://arxiv.org/abs/2512.00176
- PDF: https://arxiv.org/pdf/2512.00176
- Provenance: arxiv

## Abstract

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.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.