{"ID":2835665,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.00176","arxiv_id":"2512.00176","title":"Approximating Directed Connectivity in Almost-Linear Time","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.","short_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 f...","url_abs":"https://arxiv.org/abs/2512.00176","url_pdf":"https://arxiv.org/pdf/2512.00176v1","authors":"[\"Kent Quanrud\"]","published":"2025-11-28T19:24:13Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}