Projects per year
Abstract
The vertex connectivity of an medge nvertex 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 language  English 

Title of host publication  Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing 
Editors  Samir Khuller, Virginia Vassilevska Williams 
Place of Publication  New York, NY, USA 
Publisher  ACM 
Pages  317–329 
Number of pages  13 
ISBN (Print)  9781450380539 
DOIs  
Publication status  Published  15 Jun 2021 
MoE publication type  A4 Article in a conference publication 
Event  ACM Symposium on Theory of Computing  Virtual, Online Duration: 21 Jun 2021 → 25 Jun 2021 
Publication series
Name  STOC 2021 

Publisher  Association for Computing Machinery 
Conference
Conference  ACM Symposium on Theory of Computing 

Abbreviated title  STOC 
City  Virtual, Online 
Period  21/06/2021 → 25/06/2021 
Keywords
 vertex connectivity
 algorithmic graph theory
Projects
 1 Active

ALGOCom: Novel Algorithmic Techniques through the Lens of Combinatorics
Chalermsook, P., Spoerhase, J., Orgo, L. & Yingchareonthawornchai, S.
01/02/2018 → 31/01/2024
Project: EU: ERC grants