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 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 ( m α ) time for any α ≥ 1, if there is a m α -time maxflow algorithm. Using the current best maxflow algorithm that runs in m 4/3+ o (1) time (Kathuria, Liu and Sidford, FOCS 2020), this yields a m 4/3+ o (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 Õ( mn )-time algorithm due to Henzinger, Rao, and Gabow (FOCS 1996). Indeed, no algorithm with an o ( mn ) running time was known before our work, even if we assume an ( m )-time maxflow algorithm. Our new technique is robust enough to also improve the best Õ( mn )-time bound for directed vertex connectivity to mn 1−1/12+ o (1) time

Authors

• Jason Li 0006
• Danupon Nanongkai
• Debmalya Panigrahi
• Thatchaphol Saranurak
• Sorrachai Yingchareonthawornchai

Keywords

• algorithmic graph theory
• vertex connectivity