# Deterministic Mincut in Almost-Linear Time

arXiv: https://arxiv.org/abs/2106.05513 · HTML: https://mlsanity.com/paper/2106.05513/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Jun 2021.

## Built on by (most cited first, 2 of 2)

- [Expander Hierarchies for Normalized Cuts on Graphs](https://mlsanity.com/paper/2406.14111/) (2024)
- [Agentic Algorithm Engineering: Improving Shared-Memory Exact Minimum Cuts](https://mlsanity.com/paper/2609.07204/) (2026)

## Abstract (arXiv)

We present a deterministic (global) mincut algorithm for weighted, undirected graphs that runs in m1+o(1) time, answering an open question of Karger from the 1990s. To obtain our result, we de-randomize 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.