Vertex Connectivity in Poly-logarithmic Max-Flows

The vertex connectivity of an m-edge n-vertex undirected graph is the smallest number of vertices whose removal disconnects the graph or leaves only a singleton vertex. In 1974, Aho Hopcroft and Ullman asked if vertex connectivity can be computed in linear time. Despite the substantial effort in the past five decades, the best-known running time is Õ(mn) by Henzinger-Rao-Gabow (FOCS 1996). Indeed, no algorithm with an o(mn) running time is known even if we assume a linear-time max-flow algorithm. In this article, we give an affirmative answer to this long-standing open problem (up to a sub-polynomial factor). We present a randomized reduction from the vertex connectivity problem to the max-flow problem which incurs only a poly-logarithmic overhead in runtime. Using this reduction, we can solve vertex connectivity in almost linear time by using the celebrated almost-linear-time max-flow algorithms by Chen-Kyng-Liu-Peng-Probst Gutenberg-Sachdeva (FOCS 2022) and Brand-Chen-Kyng-Liu-Peng-Probst Gutenberg-Sachdeva-Sidford (FOCS 2023). Using our new techniques, we also obtain an algorithm for directed vertex connectivity with a running time of n²+o(1⁾ time which improves the best-known bound of Õ(mn) by Henzinger-Rao-Gabow (FOCS 1996).

Duke Scholars

Author Debmalya Panigrahi Computer Science