aalto1 untyped-item.component.html
Deterministic Small Vertex Connectivity in Almost Linear Time
Loading...
Access rights
openAccess
acceptedVersion
URL
Journal Title
Journal ISSN
Volume Title
A4 Artikkeli konferenssijulkaisussa
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Date
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
Series
Proceedings of 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pp. 789-800, Annual Symposium on Foundations of Computer Science
Abstract
In the vertex connectivity problem, given an undirected n-vertex m-edge 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 well-studied 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 quadratic-time barrier and, very recently, culminated in an almost-linear time algorithm via the recently announced max-flow 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 subquadratic-time deterministic algorithm for any constant c>3. In this paper, we give the first deterministic almost-linear time vertex connectivity algorithm for all constants c. Our running time is m1+o(1)2O(c2) time, which is almost-linear 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 almost-linear 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.
Description
| openaire: EC/H2020/759557/EU//ALGOCom
Keywords
Other note
Citation
Saranurak, T & Yingchareonthawornchai, S 2022, Deterministic Small Vertex Connectivity in Almost Linear Time. in Proceedings of 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS). Annual Symposium on Foundations of Computer Science, IEEE, pp. 789-800, Annual Symposium on Foundations of Computer Science, Denver, Colorado, United States, 31/10/2022. https://doi.org/10.1109/FOCS54457.2022.00080