We give a deterministic algorithm for computing a global minimum vertex cut in a vertex-weighted graph n vertices and m edges in O (mn) time. This breaks the long-standing (n^4) -time barrier in dense graphs, achievable by trivially computing all-pairs maximum flows. Up to subpolynomial factors, we match the fastest randomized O (mn) -time algorithm by Henzinger, Rao, and Gabow'00, and affirmatively answer the question by Gabow'06 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 O (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 O (m (n+^2) ) Even'75, O (m (n+) ) Gabow'06, and O (m2^O (^{2) }) Saranurak and Yingchareonthawornchai'22. Recently, a linear-time algorithm has been shown by Korhonen'24 for very small. Our approach applies the common-neighborhood clustering, recently introduced by Blikstad, Jiang, Mukhopadhyay, Yingchareonthawornchai'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 Wigderson and Zuckerman'99; TaShma, Umans and Zuckerman'01 and selectors based on linear lossless condensers Guruswwami, Umans and Vadhan'09; Cheraghchi'11. To our knowledge, this is the first application of selectors in graph algorithms.
Jiang et al. (Wed,) studied this question.