We developed new tools for vertex Min-cut problems, leading to several breakthrough results.

1. For the most general weighted directed vertex Min-cut problem, we present a deterministic algorithm with an almost time complexity, matching the running time of the current best randomized algorithm by [HRG, FOCS’96]. Previously, only trivial algorithms (running max flows) were known.
2. For undirected unweighted graphs, we provide a deterministic algorithm with an almost time complexity, where is the vertex connectivity of the graph. This result subsumes all previous results—(n+k^2)mn^{0.5}mkm2^{O(k^2)} [SY, FOCS’22]—up to subpolynomial factors.
3. In parallel and distributed models, we provide an almost perfect reduction of undirected unweighted vertex connectivity to max-flow. Previously, such a reduction was only known in the sequential model [LNPSY, STOC’21]. At the heart of our algorithms is a new graph decomposition technique called common-neighborhood clustering. Like many graph decomposition techniques, it serves as a versatile tool for parallelization and derandomization. In this talk, we will focus on introducing this tool by providing a simple framework for computing vertex connectivity, which can be extended to all of our results by combining it with the appropriate model-related tools.