Theory Seminar: Kent Quanrud, "Approximating Directed Connectivity in Almost-Linear Time."
- Sponsor
- Research Area of Theory and Algorithms
- Speaker
- Kent Quanrud
- Contact
- Makrand Sinha
- msinha@illinois.edu
- Originating Calendar
- Siebel School Speakers Calendar
Abstract: We present randomized algorithms that compute (1+ε)-approximate minimum global edge and vertex cuts in weighted directed graphs in O(log⁴(n)/ε) and O(log⁵(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.