## 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 m4/3+o(1) time (Kathuria, Liu and Sidford, FOCS 2020), this yields a m4/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 O(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 O(mn)-time bound for directed vertex connectivity to mn1-1/12+o(1) time

### Duke Scholars

## Published In

## DOI

## ISSN

## Publication Date

## Start / End Page

### Citation

*Proceedings of the Annual ACM Symposium on Theory of Computing*, 317–329. https://doi.org/10.1145/3406325.3451088

*Proceedings of the Annual ACM Symposium on Theory of Computing*, June 15, 2021, 317–29. https://doi.org/10.1145/3406325.3451088.

*Proceedings of the Annual ACM Symposium on Theory of Computing*, June 2021, pp. 317–29.

*Scopus*, doi:10.1145/3406325.3451088.