Deterministic Vertex Connectivity via Common-Neighborhood Clustering and Pseudorandomness

We give a deterministic algorithm for computing a global minimum vertex cut in a vertex-weighted graph with n vertices and m edges in Ô(mn) time. We use Õ(·) and Ô· to hide log(n) and no(1) factors, respectively. This breaks the long-standing Ω(n4)-time barrier in dense graphs, achievable by trivially computing all-pairs maximum flows. Up to subpolynomial factors, we match the fastest randomized Õ(mn)-time algorithm by [Henzinger, Rao and Gabow FOCS’96], and affirmatively answer the question by [Gabow FOCS’00] whether deterministic O(mn)-time algorithms exist even for unweighted graphs. Our algorithm works in directed graphs, too. In unweighted undirected graphs, we present a faster deterministic Ô(mκ)-time algorithm where κ≤ n is the size of the global minimum vertex cut. For a moderate value of κ, this strictly improves upon all previous deterministic algorithms in unweighted graphs with running time Ô(m(n+κ2)) [Even’75], Ô(m(n+κ√n)) [Gabow FOCS’00], and Ô(m2O(κ2)) [Saranurak and Yingchareonthawornchai FOCS’22]. Recently, a linear-time algorithm has been shown by [Korhonen’24] for small κ. Our approach applies the common-neighborhood clustering, recently introduced by [Blikstad, Jiang, Mukhopadhyay and Yingchareonthawornchai STOC’25], in novel ways, e.g., on top of weighted graphs and on top of vertex-expander decomposition. We also exploit pseudorandom objects often used in computational complexity communities, including crossing families based on dispersers from [TaShma, Umans and Zuckerman STOC’01, Wigderson and Zuckerman Combinatorica’99] and selectors based on linear lossless condensers [Cheraghchi’11, Guruswami, Umans and Vadhan JACM’09]. To our knowledge, this is the first application of selectors in graph algorithms.