<p>@JeffE,  Here is a paper that <a href="http://dx.doi.org/10.1016/0020-0190%2894%2900202-A" rel="nofollow">counts min weight cycles</a> 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.</p>

CC BY-SA 3.0
2012-08-29T03:12:36.180Z
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.
Tyson Williams
CC BY-SA 2.5
2011-02-07T02:52:06.067Z
2011-02-07T02:52:06.067Z
V Vinay
<p>I just taught the <a href="http://portal.acm.org/citation.cfm?id=234534" rel="nofollow noreferrer">Karger-Stein randomized mincut algorithm</a> in my graduate algorithms class.  This is a real <a href="https://cstheory.stackexchange.com/questions/189/algorithms-from-the-book">algorithmic gem</a>, so I can't <em>not</em> 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.)</p>

<p>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 <em>twice</em> 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.)</p>

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

CC BY-SA 2.5
2010-10-24T00:42:52.953Z
Nice question, Jeff !
Suresh Venkat
CC BY-SA 2.5
2010-10-26T14:12:44.553Z
Is that a tumbleweed?
Jeffε
CC BY-SA 2.5
2010-10-26T14:42:05.090Z
not sure what you mean
Suresh Venkat
CC BY-SA 2.5
2010-10-26T14:53:30.213Z
also, what would you consider an example of branching amplification ?
Suresh Venkat
CC BY-SA 2.5
2010-10-26T14:59:44.847Z
http://en.wikipedia.org/wiki/Tumbleweed#Symbolism
jbapple
CC BY-SA 2.5
2010-10-26T22:04:55.100Z
tumbleweed is also a badge on this site, which certainly doesn't apply to your question, @JeffE!
Lev Reyzin
CC BY-SA 2.5
2010-10-28T05:09:07.647Z
@Suresh: Sorry if my terminology is unclear.  The point of the Karger-Stein *branching* algorithm (reduce and recurse twice) is to *amplify* the probability of success from $1/n^2$ to $1/\log n$ without running a quadratic number of independent trials.  Hence "branching amplification".
Jeffε
CC BY-SA 2.5
2010-10-28T05:59:14.937Z
a thought: while the connection is tenuous, Raz's parallel repetition theorem has the same effect (of exponentially increasing the success rate using parallel "rounds"). It'll take a lot more reading before I can figure if there's a real connection
Suresh Venkat
<ds.algorithms><reference-request><randomized-algorithms><teaching>
Other applications of Karger-Stein branching amplification?
Jeffε
# Other applications of Karger-Stein branching amplification?

(Asked by: username_0 on 2010-10-23)

I just taught the [Karger-Stein randomized mincut algorithm](http://portal.acm.org/citation.cfm?id=234534) in my graduate algorithms class. This is a real [algorithmic gem](https://cstheory.stackexchange.com/questions/189/algorithms-from-the-book), 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.

**Tags:** ds.algorithms, reference-request, randomized-algorithms, teaching
> **Comments:**
> **username_1**: Nice question, Jeff !  
> **username_0**: Is that a tumbleweed?  
> **username_1**: not sure what you mean  
> **username_1**: also, what would you consider an example of branching amplification ?  
> **username_2**: http://en.wikipedia.org/wiki/Tumbleweed#Symbolism  
> **username_3**: tumbleweed is also a badge on this site, which certainly doesn't apply to your question, @JeffE!  
> **username_0**: @Suresh: Sorry if my terminology is unclear.  The point of the Karger-Stein *branching* algorithm (reduce and recurse twice) is to *amplify* the probability of success from $1/n^2$ to $1/\log n$ without running a quadratic number of independent trials.  Hence "branching amplification".  
> **username_1**: a thought: while the connection is tenuous, Raz's parallel repetition theorem has the same effect (of exponentially increasing the success rate using parallel "rounds"). It'll take a lot more reading before I can figure if there's a real connection  

---

## 1 answers

### Answer by username_4 on 2011-02-07. Score: 5

@JeffE, Here is a paper that [counts min weight cycles](http://dx.doi.org/10.1016/0020-0190%2894%2900202-A) 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.

> **Comments:**
> **username_5**: 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.  

---

