# Extensions of Karger's Algorithm: Why They Fail in Theory and How They Are Useful in Practice

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 46 references that are in the map.
- First posted on arXiv 5 Oct 2021.

## Builds on (most cited first, 11 of 11)

- [Holistically-Nested Edge Detection](https://mlsanity.com/paper/1504.06375/) (2015)
- [Deep Interactive Object Selection](https://mlsanity.com/paper/1603.04042/) (2016)
- [Multimodal Style Transfer via Graph Cuts](https://mlsanity.com/paper/1904.04443/) (2019)
- [An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations](https://mlsanity.com/paper/1304.2338/) (2013)
- [Automatic 3D liver location and segmentation via convolutional neural networks and graph cut](https://mlsanity.com/paper/1605.03012/) (2016)
- [Fast Sketch Segmentation and Labeling with Deep Learning](https://mlsanity.com/paper/1807.11847/) (2018)
- [Nearly Maximum Flows in Nearly Linear Time](https://mlsanity.com/paper/1304.2077/) (2013)
- [Minimum Cut in O(mlog2 n) Time](https://mlsanity.com/paper/1911.01145/) (2019)
- [Faster Algorithms for Edge Connectivity via Random 2-Out Contractions](https://mlsanity.com/paper/1909.00844/) (2019)
- [Probabilistic Watershed: Sampling all spanning forests for seeded segmentation and semi-supervised learning](https://mlsanity.com/paper/1911.02921/) (2019)
- [A Simple Algorithm for Minimum Cuts in Near-Linear Time](https://mlsanity.com/paper/1908.11829/) (2019)

## Abstract (arXiv)

The minimum graph cut and minimum s-t-cut problems are important primitives in the modeling of combinatorial problems in computer science, including in computer vision and machine learning. Some of the most efficient algorithms for finding global minimum cuts are randomized algorithms based on Karger's groundbreaking contraction algorithm. Here, we study whether Karger's algorithm can be successfully generalized to other cut problems. We first prove that a wide class of natural generalizations of Karger's algorithm cannot efficiently solve the s-t-mincut or the normalized cut problem to optimality. However, we then present a simple new algorithm for seeded segmentation / graph-based semi-supervised learning that is closely based on Karger's original algorithm, showing that for these problems, extensions of Karger's algorithm can be useful. The new algorithm has linear asymptotic runtime and yields a potential that can be interpreted as the posterior probability of a sample belonging to a given seed / class. We clarify its relation to the random walker algorithm / harmonic energy minimization in terms of distributions over spanning forests. On classical problems from seeded image segmentation and graph-based semi-supervised learning on image data, the method performs at least as well as the random walker / harmonic energy minimization / Gaussian processes.