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$ – Suresh Venkat Oct 24 '10 at 0:42
  • $\begingroup$ Is that a tumbleweed? $\endgroup$ – Jeffε Oct 26 '10 at 14:12
  • $\begingroup$ not sure what you mean $\endgroup$ – Suresh Venkat Oct 26 '10 at 14:42
  • $\begingroup$ also, what would you consider an example of branching amplification ? $\endgroup$ – Suresh Venkat Oct 26 '10 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 '10 at 22:04

@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$ – Tyson Williams Aug 29 '12 at 3:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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