Vertex Connectivity via Local Computation: Breaking Quadratic Time, Poly-logarithmic Max-flows, and Derandomization

Vertex connectivity is a classic graph-theoretic notion, that roughly measures the robustness of a network against vertex failure. Vertex connectivity k of an n-vertex m-edge graph is the minimum number of vertices to be removed to disconnect the graph. A major open problem asked almost 50 years ago is whether or not vertex connectivity can be computed in linear time [Aho, Hopcroft, and Ullman 1974, Problem 5.30]. Vertex connectivity can be solved in linear time when k =1 and k = 2 using a depth-first search tree [Tarjan'72] and a basic data structure called SPQR tree [Hopcroft and Tarjan'73], respectively. When k >2, it remains an open problem. For general connectivity, the fastest known algorithms take time O(mn) [Henziner, Rao and Gabow FOCS'96] and O(T(n)+nT(k)) [Linial, Lovász, Wigderson FOCS'86] where T(n) is the time to multiply two n-by-n matrices. Even for the special case when k = O(1) and m = O(n), both algorithms run at least n2 time. In this case, the quadratic time barrier was known 50 years ago [Kleitman'69]. In this thesis, we break the long-standing quadratic time barrier and affirmatively resolve the open problem by Aho, Hopcroft, and Ullman (up to a sub-polynomial factor). We show the following results: 1. An O(m+nk3)-time randomized algorithm. The algorithm takes O(m+n) time whenever k is sufficiently small. Here, the poly-logarithmic factor in the running time is omitted. 2. A randomized reduction to poly-logarithmic number of many calls to a max-flow algorithm. Thus, vertex connectivity can be solved in almost linear time by using the almost linear time max-flow algorithm [Chen, Kyng, Liu, Peng, Probst and Sachdeva FOCS'22]. 3. An almost linear time deterministic algorithm whenever k is sufficiently small. To achieve these results, we introduce local computation frameworks that could be potentially extended beyond vertex connectivity. We show that fast local cut computation implies fast vertex connectivity and develop fast local cut detection algorithms that lead to the O(m+nk3)-time vertex connectivity algorithm. By making a connection to the theory of kernelization, we solve vertex connectivity in poly-logarithmic max-flows. Finally, we use vertex expanders and vertex cut sparsifiers to derandomize the vertex connectivity algorithm for small vertex connectivity.