# Practical Minimum Cut Algorithms

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Aug 2017.

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

- [Agentic Algorithm Engineering: Improving Shared-Memory Exact Minimum Cuts](https://mlsanity.com/paper/2609.07204/) (2026)

## Abstract (arXiv)

The minimum cut problem for an undirected edge-weighted graph asks us to divide its set of nodes into two blocks while minimizing the weight sum of the cut edges. Here, we introduce a linear-time algorithm to compute near-minimum cuts. Our algorithm is based on cluster contraction using label propagation and Padberg and Rinaldi's contraction heuristics [SIAM Review, 1991]. We give both sequential and shared-memory parallel implementations of our algorithm. Extensive experiments on both real-world and generated instances show that our algorithm finds the optimal cut on nearly all instances significantly faster than other state-of-the-art algorithms while our error rate is lower than that of other heuristic algorithms. In addition, our parallel algorithm shows good scalability.