Deterministic k-Vertex Connectivity in k^2 Max-flows
share
An n-vertex m-edge graph is k-vertex connected if it cannot be disconnected by deleting less than k vertices. After more than half a century of intensive research, the result by [Li et al. STOC'21] finally gave a randomized algorithm for checking k-connectivity in near-optimal O(m) time. (We use O(·) to hide an n^o(1) factor.) Deterministic algorithms, unfortunately, have remained much slower even if we assume a linear-time max-flow algorithm: they either require at least Ω(mn) time [Even'75; Henzinger Rao and Gabow, FOCS'96; Gabow, FOCS'00] or assume that k=o(√(log n)) [Saranurak and Yingchareonthawornchai, FOCS'22]. We show a deterministic algorithm for checking k-vertex connectivity in time proportional to making O(k^2) max-flow calls, and, hence, in O(mk^2) time using the deterministic max-flow algorithm by [Brand et al. FOCS'23]. Our algorithm gives the first almost-linear-time bound for all k where √(log n)≤ k≤ n^o(1) and subsumes up to a sub polynomial factor the long-standing state-of-the-art algorithm by [Even'75] which requires O(n+k^2) max-flow calls. Our key technique is a deterministic algorithm for terminal reduction for vertex connectivity: given a terminal set separated by a vertex mincut, output either a vertex mincut or a smaller terminal set that remains separated by a vertex mincut. We also show a deterministic (1+ϵ)-approximation algorithm for vertex connectivity that makes O(n/ϵ^2) max-flow calls, improving the bound of O(n^1.5) max-flow calls in the exact algorithm of [Gabow, FOCS'00]. The technique is based on Ramanujan graphs.
READ FULL TEXT