Graphs

We prove impossibility results showing that Karger’s contraction algorithm cannot be extended to $s$-$t$-mincuts or normalized cuts. However, we show how extensions of Karger’s algorithm can still be useful for seeded segmentation.

The Karger-Stein algorithm is an improvement over Karger’s beautiful contraction algorithm for minimum graph cuts. In this post, I show how it finds the perfect tradeoff between finding a mincut with high probability and finding it quickly. In the course of doing so, we will also understand where the somewhat opaque factor of sqrt(2) comes from.