[Theory] UC Theory Seminar: a reminder

[Alexander Razborov]

Departments of Mathematics & Computer Science
Combinatorics & Theory Seminar

Tuesday, April 23
Ry 251@ 3:30pm

Thatchaphol Saranurak
(TTIC)

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]. 

In this talk, I will present a randomized Monte Carlo algorithm with ~O(m + k^3 n) time. This algorithm proves the conjecture by Aho, Hopcroft, and Ullman when k=O(1) up to a polylog factor, breaks the 50-year-old bound by Kleitman, is fastest for 4 < 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 key to our results is to avoid computing single-source connectivity, which was needed
by all previous exact algorithms and is not known to admit o(n^2) time. Instead, we design the first 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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20190422/04585f7b/attachment.html>