Vertex Connectivity in Poly-Logarithmic Max-Flows

No Thumbnail Available
Journal Title
Journal ISSN
Volume Title
Conference article in proceedings
This publication is imported from Aalto University research portal.
View publication in the Research portal

Other link related to publication
Date
2021-06-15
Major/Subject
Mcode
Degree programme
Language
en
Pages
317–329
Series
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021
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
Description
| openaire: EC/H2020/759557/EU//ALGOCom
Keywords
vertex connectivity, algorithmic graph theory
Other note
Citation
Li , J , Nanongkai , D , Panigrahi , D , Saranurak , T & Yingchareonthawornchai , S 2021 , Vertex Connectivity in Poly-Logarithmic Max-Flows . in S Khuller & V V Williams (eds) , Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing . STOC 2021 , ACM , New York, NY, USA , pp. 317–329 , ACM Symposium on Theory of Computing , Virtual, Online , 21/06/2021 . https://doi.org/10.1145/3406325.3451088