
<html><head><meta http-equiv="content-type" content="text/html; charset=utf-8"></head><body dir="auto"><div dir="ltr"><span style="background-color: rgba(255, 255, 255, 0);">Departments of Mathematics & Computer Science<br>Combinatorics & Theory Seminar<br><br><a href="x-apple-data-detectors://0" dir="ltr" x-apple-data-detectors="true" x-apple-data-detectors-type="calendar-event" x-apple-data-detectors-result="0" style="-webkit-text-decoration-color: rgba(0, 0, 0, 0.258824);">Tuesday, April 23</a><br>Ry 251@ <a href="x-apple-data-detectors://1" dir="ltr" x-apple-data-detectors="true" x-apple-data-detectors-type="calendar-event" x-apple-data-detectors-result="1" style="-webkit-text-decoration-color: rgba(0, 0, 0, 0.258824);">3:30pm</a><br><br>Thatchaphol Saranurak<br>(TTIC)<br><br>Title: Breaking Quadratic Time for Small Vertex Connectivity <br><br>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]. </span></div><div><span style="background-color: rgba(255, 255, 255, 0);"><br></span></div><div><span style="background-color: rgba(255, 255, 255, 0);">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).</span></div><div><span style="background-color: rgba(255, 255, 255, 0);"><br></span></div><div><div><span style="background-color: rgba(255, 255, 255, 0);">The key to our results is to avoid computing single-source connectivity, which was needed</span></div><div><span style="background-color: rgba(255, 255, 255, 0);">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.</span></div></div><div><span style="background-color: rgba(255, 255, 255, 0);"><br></span></div><div><span style="background-color: rgba(255, 255, 255, 0);">This talk is based on joint works with Danupon Nanongkai and Sorrachai Yingchareonthawornchai.</span></div><div dir="ltr"></div></body></html>