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

Abstract

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. Secondly, we present a new algorithm for seeded segmentation / graph-based semi-supervised learning with an asymptotic runtime linear in the number of edges of the graph. This extremely simple algorithm closely follows Karger’s original algorithm. It also yields a potential that can be interpreted as the posterior probability of a sample belonging to a given seed / class. We clarify the 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.