New Tools and Faster Algorithms for Vertex Min-cut

1. For the most general weighted directed vertex connectivity problem, we present a deterministic algorithm with an almost $mn$ time complexity, matching the running time of the current best randomized algorithm by [HRG, FOCS’96]. Previously, only trivial algorithms (running $n^2$ max flows) were known.

2. For undirected unweighted graphs, we provide a deterministic algorithm with an almost $mk$ time complexity, where $k$ is the vertex connectivity of the graph. This result subsumes all previous results—$(n+k^2)m$ [Even’75], $n^{0.5}mk$ [Gabow, FOCS’00], $m2^{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.