我们提出了一种确定性算法，用于在具有$n$个顶点和$m$条边的顶点加权图中计算全局最小顶点割，时间复杂度为$\widehat O(mn)$。这一结果打破了稠密图中长期存在的$\widehat \Omega(n^{4})$时间复杂度障碍（通过简单地计算所有顶点对的最大流可以实现）。在亚多项式因子范围内，我们匹配了由[Henzinger, Rao, 和 Gabow'00]提出的最快的随机化$\tilde O(mn)$时间算法，并肯定回答了[Gabow'06]提出的问题，即是否存在确定性的$O(mn)$时间算法，即使对于无权图也是如此。我们的算法适用于有向图。对于无权无向图，我们提出了一个更快的确定性$\widehat O(m\kappa)$时间算法，其中$\kappa\leq n$是全局最小顶点割的大小。当$\kappa$值适中时，这严格优于之前所有无权图中的确定性算法，其运行时间为$\widehat O(m(n+\kappa^{2}))$[Even'75]、$\widehat O(m(n+\kappa\sqrt{n}))$[Gabow'06]以及$\widehat O(m2^{O(\kappa^{2})})$[Saranurak 和 Yingchareonthawornchai'22]。最近，[Korhonen'24]展示了针对非常小的$\kappa$的线性时间算法。我们的方法以新颖的方式应用了[Blikstad, Jiang, Mukhopadhyay, Yingchareonthawornchai'25]最近引入的公共邻居聚类技术，例如在加权图和顶点扩张分解之上。我们还利用了计算复杂性社区常用的伪随机对象，包括基于[Wigderson 和 Zuckerman'99；TaShma, Umans 和 Zuckerman'01]分散器的交叉家族和基于[Guruswami, Umans 和 Vadhan'09；Cheraghchi'11]线性无损压缩器的选择器。据我们所知，这是选择器首次应用于图算法。

We give a deterministic algorithm for computing a global minimum vertex cut in a vertex-weighted graph $n$ vertices and $m$ edges in $\widehat O(mn)$ time. This breaks the long-standing $\widehat \Omega(n^{4})$-time barrier in dense graphs, achievable by trivially computing all-pairs maximum flows. Up to subpolynomial factors, we match the fastest randomized $\tilde 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 $\widehat O(m\kappa)$-time algorithm where $\kappa\le n$ is the size of the global minimum vertex cut. For a moderate value of $\kappa$, this strictly improves upon all previous deterministic algorithms in unweighted graphs with running time $\widehat O(m(n+\kappa^{2}))$ [Even'75], $\widehat O(m(n+\kappa\sqrt{n}))$ [Gabow'06], and $\widehat O(m2^{O(\kappa^{2})})$ [Saranurak and Yingchareonthawornchai'22]. Recently, a linear-time algorithm has been shown by [Korhonen'24] for very small $\kappa$. 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.