Deterministic Mincut in Almost-Linear Time

We present a deterministic (global) mincut algorithm for weighted, undirected graphs that runs in m(1)(+o(1)) time, answering an open question of Karger from the 1990s. To obtain our result, we derandomize the construction of the skeleton graph in Karger's near-linear time mincut algorithm, which is its only randomized component. In particular, we partially de-randomize the well-known Benczur-Karger graph sparsification technique by random sampling, which we accomplish by the method of pessimistic estimators. Our main technical component is designing an efficient pessimistic estimator to capture the cuts of a graph, which involves harnessing the expander decomposition framework introduced in recent work by Goranci et al. (SODA 2021). As a side-effect, we obtain a structural representation of all approximate mincuts in a graph, which may have future applications.

Automated summary

This study presents a deterministic mincut algorithm for weighted, undirected graphs, answering a question from Karger. By partially derandomizing the Benczur-Karger graph sparsification technique and designing an efficient pessimistic estimator to capture graph cuts, as well as utilizing the expander decomposition framework, the researchers achieved the desired result. As a side-effect, a structural representation of all approximate mincuts in a graph was obtained, potentially useful for future applications.