Kargar’s Algorithm

A graph cut is a partition of a graph into 2 non-empty partition. We say that an edge crosses a cut if it goes from one partition to the other. The minimum graph cut is the cut with the fewest edges crossing it.

Algorithm

Kargar’s algorithm attempts to find a minimum graph cut in the following manner:

1. Pick a random edge
2. Contract it (i.e. merge its two vertices into one)
3. Repeat under only 2 vertices left
4. Return cut corresponding to the 2 partitions of vertices

Theorem

Theorem: The probability that Kargar’s algorithm returns the min cut in a graph with \(N\) vertices is \(\geq 2 / n(n-1)\).

For comparison, the probability that a random cut is the mincut can be as small as \(2^{-\Omega(N)}\). What’s the intuition? Suppose \(C\) is a mincut (there might be more than 1!). Kargar’s algorithm will fail only if it contracts an edge crossing \(C\). But this isn’t too likely to happen since there are relatively few edges in \(C\).

Proof: Let \(C\) be a min-cut and denote the edges that Kargar’s algorithm contracts as \(e_1,..., e_{n-2}\). Let \(E_i\) be event that \(e_i\) does not cross \(C\). In order to successfully return a mincut, all \(E\) need to occur:

\[\mathbb{P}[E_1 \land E_2 \land ... \land E_{n-2}] = \mathbb{P}[E_1] \mathbb{P}[E_1 | E_2] ... \mathbb{P}[E_{n-1}| E_{<n-2}]\]

Consider a single step:

\[\mathbb{P}[E_j | E_{<j}] = 1 - \mathbb{P}[\neg E_j |E_{<j}]\]

The term on the right is the probability of crossing cut \(e_j\), given that no previous edges crossed the cut. The probability whether we cut \(e_j\) will be the number of edges remaining in the cut of the contracted graph divided by the number of edges in the contracted graph after contracted \(j-1\) edges. This means that the number of edges remaining is lower bounded by:

\[\text{\# edges remaining} \geq \text{\# vertices remaining} \text{min degree of any vertex} / 2\]

which is lower bounded by:

\[\geq (n - j + 1) (\text{\# edges crossing C}) / 2\]

Thus:

\[1 - \mathbb{P}[\neg E_j |E_{<j}] \geq \frac{n-j-1}{n-j+1}\]

Returning to consider the full chain of steps:

\[\mathbb{P}[E_1 \land E_2 \land ... \land E_{n-2}] \geq \frac{n-2}{n} \frac{n-3}{n-1} ... \frac{1}{3} = \frac{2}{n(n-1)}\]

Improved Algorithm

To do better, we can run Kargar’s algorithm \(n (n-1) \log \delta\) times and take the smallest cut. This will find the mincut with probability \(1-\delta\).