
<html><head><meta http-equiv="content-type" content="text/html; charset=utf-8"></head><body dir="auto"><div dir="ltr"><span style="-webkit-text-size-adjust: auto;">Departments of Mathematics & Computer Science</span><br><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"></div></div><span style="-webkit-text-size-adjust: auto;">Combinatorics & Theory Seminar</span><br style="-webkit-text-size-adjust: auto;"><span style="-webkit-text-size-adjust: auto;"></span><br style="-webkit-text-size-adjust: auto;"><span style="-webkit-text-size-adjust: auto;">Tuesday, <b>October 11, 3:30pm</b></span><br style="-webkit-text-size-adjust: auto;"><span style="-webkit-text-size-adjust: auto;">Location <b>Кеnt 107</b></span><br style="-webkit-text-size-adjust: auto;"><br>SPEAKER: Sorrachai Yingchareonthawornchai (Aalto University, Finland)<br style="-webkit-text-size-adjust: auto;"><span style="-webkit-text-size-adjust: auto;"></span><br style="-webkit-text-size-adjust: auto;"><span style="-webkit-text-size-adjust: auto;">TITLE: </span>Deterministic Small Vertex Connectivity in Almost Linear Time<br style="-webkit-text-size-adjust: auto;"><span style="-webkit-text-size-adjust: auto;"></span><br style="-webkit-text-size-adjust: auto;"><span style="-webkit-text-size-adjust: auto;">ABSTRACT:<font face="Arial, sans-serif"><span style="white-space: pre-wrap;"> </span></font></span><span style="-webkit-text-size-adjust: auto; background-color: rgb(255, 255, 255);">In the vertex connectivity problem, given an undirected n-vertex</span><br style="-webkit-text-size-adjust: auto;"><span style="-webkit-text-size-adjust: auto; background-color: rgb(255, 255, 255);">m-edge graph, we need to compute the minimum number of vertices</span><br style="-webkit-text-size-adjust: auto;"><span style="-webkit-text-size-adjust: auto; background-color: rgb(255, 255, 255);">that can disconnect the graph after removing them. This problem is one</span><br style="-webkit-text-size-adjust: auto;"><span style="-webkit-text-size-adjust: auto; background-color: rgb(255, 255, 255);">of the most well-studied graph problems. From 2019, a new line of</span><br style="-webkit-text-size-adjust: auto;"><span style="-webkit-text-size-adjust: auto; background-color: rgb(255, 255, 255);">work [Nanongkai et al. STOC'19;SODA'20;STOC'21] has used</span><br style="-webkit-text-size-adjust: auto;"><span style="-webkit-text-size-adjust: auto; background-color: rgb(255, 255, 255);">randomized techniques to break the quadratic-time barrier and, very</span><br style="-webkit-text-size-adjust: auto;"><span style="-webkit-text-size-adjust: auto; background-color: rgb(255, 255, 255);">recently, culminated in an almost-linear time algorithm via the recently</span><br style="-webkit-text-size-adjust: auto;"><span style="-webkit-text-size-adjust: auto; background-color: rgb(255, 255, 255);">announced maxflow algorithm by Chen et al. In contrast, all known deterministic algorithms are much slower. The fastest algorithm [Gabow</span><br style="-webkit-text-size-adjust: auto;"><span style="-webkit-text-size-adjust: auto; background-color: rgb(255, 255, 255);">FOCS'00] takes O(m(n+\min\{c^{5/2},cn^{3/4}\})) time where c</span><br style="-webkit-text-size-adjust: auto;"><span style="-webkit-text-size-adjust: auto; background-color: rgb(255, 255, 255);">is the vertex connectivity. It remains open whether there exists a subquadratic-time deterministic algorithm for any constant</span><br style="-webkit-text-size-adjust: auto;"><span style="-webkit-text-size-adjust: auto; background-color: rgb(255, 255, 255);">c>3.</span><br style="-webkit-text-size-adjust: auto;"><br style="-webkit-text-size-adjust: auto;"><span style="-webkit-text-size-adjust: auto; background-color: rgb(255, 255, 255);">In this talk, we present the first deterministic almost-linear time</span><br style="-webkit-text-size-adjust: auto;"><span style="-webkit-text-size-adjust: auto; background-color: rgb(255, 255, 255);">vertex connectivity algorithm for all constants c. Our</span><br style="-webkit-text-size-adjust: auto;"><span style="-webkit-text-size-adjust: auto; background-color: rgb(255, 255, 255);">running time is m^{1+o(1)}2^{O(c^{2})} time, which is almost-linear</span><br style="-webkit-text-size-adjust: auto;"><span style="-webkit-text-size-adjust: auto; background-color: rgb(255, 255, 255);">for all c=o(\sqrt{\log n}). This is the first deterministic algorithm</span><br style="-webkit-text-size-adjust: auto;"><span style="-webkit-text-size-adjust: auto; background-color: rgb(255, 255, 255);">that breaks the O(n^{2})-time bound on sparse graphs where m=O(n), which is known for more</span><br style="-webkit-text-size-adjust: auto;"><span style="-webkit-text-size-adjust: auto; background-color: rgb(255, 255, 255);">than 50 years ago [Kleitman'69].</span><br style="-webkit-text-size-adjust: auto;"><br style="-webkit-text-size-adjust: auto;"><span style="-webkit-text-size-adjust: auto; background-color: rgb(255, 255, 255);">Towards our result, we give a new reduction framework to vertex</span><br style="-webkit-text-size-adjust: auto;"><span style="-webkit-text-size-adjust: auto; background-color: rgb(255, 255, 255);">expanders which in turn exploits our new almost-linear time construction</span><br style="-webkit-text-size-adjust: auto;"><span style="-webkit-text-size-adjust: auto; background-color: rgb(255, 255, 255);">of mimicking network for vertex connectivity. The</span><br style="-webkit-text-size-adjust: auto;"><span style="-webkit-text-size-adjust: auto; background-color: rgb(255, 255, 255);">previous construction by Kratsch and Wahlstr\"{o}m [FOCS'12]</span><br style="-webkit-text-size-adjust: auto;"><span style="-webkit-text-size-adjust: auto; background-color: rgb(255, 255, 255);">requires large polynomial time and is randomized.</span><br style="-webkit-text-size-adjust: auto;"><span style="-webkit-text-size-adjust: auto; background-color: rgb(255, 255, 255);">An interesting aspect that allows our overall algorithm to be efficient is to ``lift'' several graph problems to hypergraphs and work directly on hypergraphs.</span><br style="-webkit-text-size-adjust: auto;"><br style="-webkit-text-size-adjust: auto;"><span style="-webkit-text-size-adjust: auto; background-color: rgb(255, 255, 255);">This is joint work with Thatchaphol Saranurak. </span><br><div style="-webkit-text-size-adjust: auto; font-family: Arial, sans-serif; white-space: pre-wrap;"><p></p><br class="Apple-interchange-newline"></div></div></div></div></body></html>