Theory Seminar – Sorrachai Yingchareonthawornchai
Speaker: Sorrachai Yingchareonthawornchai
Bio: Sorrachai Yingchareonthawornchai is currently a Ph.D. student in computer science at Aalto University, Finland. He obtained an MS degree in computer science at Michigan State University in 2019. He is the recipient of the best poster award in ICNP 2016. His research interest includes graph algorithms and combinatorial optimization.
Logistics:
- Date: Tuesday, November 8, 2022
- In-person: Northwestern University Mudd Library 3514
- Virtual: via zoom
- Time: 3:30 pm ( Chicago Time)
- Video: via Panopto
Titles and Abstracts:
Title: Deterministic Small Vertex Connectivity in Almost Linear Time
Abstract: 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}\}
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.
This is joint work with Thatchaphol Saranurak.