Date & Time:
October 11, 2022 3:30 pm – 4:30 pm
Kent 107, 1020-24 East 58th St., Chicago, IL, 60637
10/11/2022 03:30 PM 10/11/2022 04:30 PM America/Chicago Sorrachai Yingchareonthawornchai (Aalto) – Deterministic Small Vertex Connectivity in Almost Linear Time Kent 107, 1020-24 East 58th St., Chicago, IL, 60637

In the vertex connectivity problem, given an undirected n-vertex m-edge graph, we need to compute the minimum number of vertices that can disconnect the graph 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 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 subquadratic-time deterministic algorithm for any constant c>3.

In this talk, we present the first deterministic almost-linear time vertex connectivity algorithm for all constants c. Our running time is m^{1+o(1)}2^{O(c^{2})} 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\”{o}m [FOCS’12] requires large polynomial time and is randomized. An interesting aspect that allows our overall algorithm to be efficient is to “lift” several graph problems to hypergraphs and work directly on hypergraphs.

Host: Janos Simon


Sorrachai Yingchareonthawornchai

Doctoral Researcher, Aalto University

I am a Doctoral Researcher at Aalto University in Espoo, Finland.

Related News & Events

Students posing at competition
UChicago CS News

UChicago Undergrad Team Places Second Overall In Regionals For World’s Largest Programming Competition

Mar 17, 2023
Haifeng Xu
UChicago CS News

New CS and DSI Faculty Haifeng Xu Brings Strategic Intelligence to NeurIPS 2022

Nov 28, 2022
UChicago CS News

UChicago CS Research Finds New Angle on Database Query Processing with Geometry

Nov 08, 2022
UChicago CS News

Asst. Prof. Aloni Cohen Receives Award For Revealing Flaws in Deidentifying Data

Sep 09, 2022
UChicago CS News

UChicago Hosts NSF Workshop on Frontiers of Quantum Advantage

Aug 15, 2022
UChicago CS News

New 2022-23 Faculty Add Expertise in Linguistics, Visualization, Economics, and Data Science Education

Aug 11, 2022
In the News

UChicago Co-Leads $10 Million NSF Institute on Foundations of Data Science

Aug 09, 2022
In the News

Bill Fefferman Comments on New Standards for Quantum-Proof Cryptography

Jul 07, 2022
UChicago CS News

UChicago London Colloquium Features Data Science, Quantum Research

Jul 01, 2022
UChicago CS News

Faculty Bill Fefferman and Chenhao Tan Receive Google Research Scholar Awards

Jun 21, 2022
UChicago CS News

First-Year PhD Student Co-Authors Outstanding Paper Award Winner at TQC 2022

Apr 28, 2022
In the News

Quanta Magazine Features Prof. Bill Fefferman’s Work on Quantum Algorithms

Jan 20, 2022
arrow-down-largearrow-left-largearrow-right-large-greyarrow-right-large-yellowarrow-right-largearrow-right-smallbutton-arrowclosedocumentfacebookfacet-arrow-down-whitefacet-arrow-downPage 1CheckedCheckedicon-apple-t5backgroundLayer 1icon-google-t5icon-office365-t5icon-outlook-t5backgroundLayer 1icon-outlookcom-t5backgroundLayer 1icon-yahoo-t5backgroundLayer 1internal-yellowinternalintranetlinkedinlinkoutpauseplaypresentationsearch-bluesearchshareslider-arrow-nextslider-arrow-prevtwittervideoyoutube