Talk by Thatchaphol Saranurak

Title:
Breaking Quadratic Time for Small Vertex Connectivity

Abstract:
Vertex connectivity a classic extensively-studied problem. Given an integer k, its goal is to decide if an n-node m-edge graph can be disconnected by removing k vertices. Although an O(m)-time algorithm was postulated since 1974 [Aho, Hopcroft, and Ullman], and despite its sibling problem of edge connectivity being resolved over two decades ago [Karger STOC’96], so far no vertex connectivity algorithms are faster than O(n^2) time even for k = 4 and m = O(n). In the simplest case where m = O(n) and k = O(1), the O(n^2) bound dates five decades back to [Kleitman IEEE Trans. Circuit Theory’69]. For the general case, the best bound is ~O( min{ kn^2 ,n^\omega + nk^\omega } ) [Henzinger, Rao, Gabow FOCS’96; Linial, Lovász, Wigderson FOCS’86].
Despite the lack of progress for decades, in this talk, I will present a simple and teachable randomized Monte Carlo algorithm with ~O(m + k^3 n) time. This algorithm proves the conjecture since 1974 when k=O(1) up to a polylog factor, breaks the 50-year-old bound by Kleitman, and is fastest for 3 < k < n^{0.456}. The story is similar for the directed graphs where we obtain an algorithm with running time at most ~O(k^2 m).

The algorithm is based on a local algorithm for computing vertex connectivity; without reading the whole graph, our algorithm can find a separator of size at most k or certify that there is no separator of size at most k "near" a given seed node. This talk is based on joint works with Danupon Nanongkai and Sorrachai Yingchareonthawornchai.

BIO
Thatchaphol Saranurak is Research Assistant Professor at Toyota Technological Institute in Chicago. He received his PhD in Computer Science from School of Computer Science and Communication (CSC), KTH Royal Institute of Technology, Sweden.
Read more