Deterministic Small Vertex Connectivity in Almost Linear Time

Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussaConference contributionScientificvertaisarvioitu

17 Lataukset (Pure)


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.
OtsikkoProceedings of 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)
ISBN (elektroninen)978-1-6654-5519-0
DOI - pysyväislinkit
TilaJulkaistu - 30 lokak. 2022
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisuussa
TapahtumaAnnual Symposium on Foundations of Computer Science - Denver, Yhdysvallat
Kesto: 31 lokak. 20223 marrask. 2022
Konferenssinumero: 63


NimiAnnual Symposium on Foundations of Computer Science
ISSN (elektroninen)2575-8454


ConferenceAnnual Symposium on Foundations of Computer Science


Sukella tutkimusaiheisiin 'Deterministic Small Vertex Connectivity in Almost Linear Time'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

Siteeraa tätä