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.