Vertex connectivity in poly-logarithmic max-flows

The vertex connectivity of an 𝑚-edge 𝑛-vertex undirected graph is the smallest number of vertices whose removal disconnects the graph, or leaves only a singleton vertex. In this paper, we give a reduction from the vertex connectivity problem to a set of maxflow instances. Using this reduction, we can solve vertex connectivity in Õ (𝑚 𝛼 ) time for any 𝛼 ≥ 1, if there is a 𝑚 𝛼 -time maxflow algorithm.

Using the current best maxflow algorithm that runs in 𝑚 4/3+𝑜 (1) time (Kathuria, Liu and Sidford, FOCS 2020), this yields a 𝑚 4/3+𝑜 (1)time vertex connectivity algorithm. This is the first improvement in the running time of the vertex connectivity problem in over 20 years, the previous best being an Õ (𝑚𝑛)-time algorithm due to Henzinger, Rao, and Gabow (FOCS 1996). Indeed, no algorithm with an 𝑜 (𝑚𝑛) running time was known before our work, even if we assume an Õ (𝑚)-time maxflow algorithm.

Our new technique is robust enough to also improve the best Õ (𝑚𝑛)-time bound for directed vertex connectivity to 𝑚𝑛 1-1/12+𝑜 (1) time

• Theory of computation → Graph algorithms analysis.