Vertex Connectivity in Poly-Logarithmic Max-Flows

Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai

Research output: Chapter in Book/Report/Conference proceedingConference article in proceedingsScientificpeer-review

22 Citations (Scopus)


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 Õ(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 mn1−1/12+o(1) time
Original languageEnglish
Title of host publicationProceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing
EditorsSamir Khuller, Virginia Vassilevska Williams
Place of PublicationNew York, NY, USA
Number of pages13
ISBN (Print)978-1-4503-8053-9
Publication statusPublished - 15 Jun 2021
MoE publication typeA4 Conference publication
EventACM Symposium on Theory of Computing - Virtual, Online
Duration: 21 Jun 202125 Jun 2021

Publication series

NameSTOC 2021
PublisherAssociation for Computing Machinery


ConferenceACM Symposium on Theory of Computing
Abbreviated titleSTOC
CityVirtual, Online


  • vertex connectivity
  • algorithmic graph theory


Dive into the research topics of 'Vertex Connectivity in Poly-Logarithmic Max-Flows'. Together they form a unique fingerprint.

Cite this