{"id":"arxiv:2512.00176","kind":"preprint","title":"Approximating Directed Connectivity in Almost-Linear Time","authors":["Kent Quanrud"],"author_count":1,"year":2025,"published":"2025-11-28","venue":null,"cited_by":null,"doi":null,"arxiv_id":"2512.00176","nct_id":null,"source_url":"https://arxiv.org/abs/2512.00176","archive_url":"https://space-kitty.com/papers/arxiv:2512.00176","updated":"2025-11-28","pmid":null,"pmcid":null,"openalex_id":null,"pdf_url":"https://arxiv.org/pdf/2512.00176","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_license":"CC0-1.0 (arXiv descriptive metadata)","license":null,"is_open_access":false,"retracted":false,"peer_reviewed":false,"categories":["cs.DS"],"details":null,"provenance":"arxiv","attribution":"Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.","topics":[],"cited_in_dossiers":[]}