I just taught the Karger-Stein randomized mincut algorithm in my graduate algorithms class. This is a real algorithmic gem, so I can't not teach it, but it always leaves me frustrated, because I don't know any other applications of the main technique. (So it's hard to assign homework that drives the point home.)

Karger and Stein's algorithm is a refinement of an earlier algorithm of Karger, which iteratively contracts random edges until the graph has only two vertices; this simple algorithm runs in $O(n^2)$ time and returns a minimum cut with probability $\Omega(1/n^2)$, where $n$ is the number of vertices in the input graph. The refined "Recursive Contraction Algorithm" iteratively contracts random edges until the number of vertices drops from $n$ to $n/\sqrt{2}$, recursively calls itself twice on the remaining graph, and returns the smaller of the two resulting cuts. A straightforward implementation of the refined algorithm runs in $O(n^2\log n)$ time and returns a minimum cut with probability $\Omega(1/\log n)$. (There are more efficient implementations of these algorithms, and better randomized algorithms.)

What other randomized algorithms use similar branching amplification techniques? I'm especially interested in examples that don't (obviously) involve graph cuts.

  • 2
    $\begingroup$ Nice question, Jeff ! $\endgroup$ Oct 24, 2010 at 0:42
  • $\begingroup$ Is that a tumbleweed? $\endgroup$
    – Jeffε
    Oct 26, 2010 at 14:12
  • $\begingroup$ not sure what you mean $\endgroup$ Oct 26, 2010 at 14:42
  • $\begingroup$ also, what would you consider an example of branching amplification ? $\endgroup$ Oct 26, 2010 at 14:53
  • 2
    $\begingroup$ tumbleweed is also a badge on this site, which certainly doesn't apply to your question, @JeffE! $\endgroup$
    – Lev Reyzin
    Oct 26, 2010 at 22:04

1 Answer 1


@JeffE, Here is a paper that counts min weight cycles in a graph. As far as I remember, it was definitely inspired by Karger's technique/result and it was a fun proof. Hope this helps with the teaching.

  • $\begingroup$ This paper does not count the number of minimum weight cycles in a graph. Instead, it gives a bound on the number of cycles whose weight is at most some constant multiple of the weight of the minimum weight cycle. $\endgroup$ Aug 29, 2012 at 3:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.