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 contributionScientificpeer-review

Abstract

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
PublisherACM
Pages317–329
Number of pages13
ISBN (Print)9781450380539
DOIs
Publication statusPublished - 15 Jun 2021
MoE publication typeA4 Article in a conference publication
EventACM Symposium on Theory of Computing - Virtual, Online
Duration: 21 Jun 202125 Jun 2021

Publication series

NameSTOC 2021
PublisherAssociation for Computing Machinery

Conference

ConferenceACM Symposium on Theory of Computing
Abbreviated titleSTOC
CityVirtual, Online
Period21/06/202125/06/2021

Keywords

  • vertex connectivity
  • algorithmic graph theory

Cite this