Projects per year
Abstract
In the vertex connectivity problem, given an undirected nvertex medge graph G, we need to compute the minimum number of vertices that can disconnect G after removing them. This problem is one of the most wellstudied graph problems. From 2019, a new line of work [Nanongkai et al.~STOC'19;SODA'20;STOC'21] has used randomized techniques to break the quadratictime barrier and, very recently, culminated in an almostlinear time algorithm via the recently announced maxflow algorithm by Chen et al. In contrast, all known deterministic algorithms are much slower. The fastest algorithm [Gabow FOCS'00] takes O(m(n+min{c^(5/2),cn^(3/4)})) time where c is the vertex connectivity. It remains open whether there exists a subquadratictime deterministic algorithm for any constant c>3.
In this paper, we give the first deterministic almostlinear time vertex connectivity algorithm for all constants c. Our running time is m1+o(1)2O(c2) time, which is almostlinear for all c=o(sqrt(log n)). This is the first deterministic algorithm that breaks the O(n^2)time bound on sparse graphs where m=O(n), which is known for more than 50 years ago [Kleitman'69]. Towards our result, we give a new reduction framework to vertex expanders which in turn exploits our new almostlinear time construction of mimicking network for vertex connectivity. The previous construction by Kratsch and Wahlström [FOCS'12] requires large polynomial time and is randomized.
In this paper, we give the first deterministic almostlinear time vertex connectivity algorithm for all constants c. Our running time is m1+o(1)2O(c2) time, which is almostlinear for all c=o(sqrt(log n)). This is the first deterministic algorithm that breaks the O(n^2)time bound on sparse graphs where m=O(n), which is known for more than 50 years ago [Kleitman'69]. Towards our result, we give a new reduction framework to vertex expanders which in turn exploits our new almostlinear time construction of mimicking network for vertex connectivity. The previous construction by Kratsch and Wahlström [FOCS'12] requires large polynomial time and is randomized.
Original language  English 

Title of host publication  Proceedings of 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) 
Publisher  IEEE 
Pages  789800 
ISBN (Electronic)  9781665455190 
DOIs  
Publication status  Published  30 Oct 2022 
MoE publication type  A4 Article in a conference publication 
Event  Annual Symposium on Foundations of Computer Science  Denver, United States Duration: 31 Oct 2022 → 3 Nov 2022 Conference number: 63 
Publication series
Name  Annual Symposium on Foundations of Computer Science 

ISSN (Electronic)  25758454 
Conference
Conference  Annual Symposium on Foundations of Computer Science 

Abbreviated title  FOCS 
Country/Territory  United States 
City  Denver 
Period  31/10/2022 → 03/11/2022 
Fingerprint
Dive into the research topics of 'Deterministic Small Vertex Connectivity in Almost Linear Time'. Together they form a unique fingerprint.Projects
 1 Active

ALGOCom: Novel Algorithmic Techniques through the Lens of Combinatorics
Chalermsook, P., Jindal, G., Franck, M., Spoerhase, J., Yingchareonthawornchai, S., Gadekar, A., Orgo, L., Jiamjitrak, W. & Khodamoradi, K.
01/02/2018 → 31/01/2024
Project: EU: ERC grants