23 Randomized Algorithms for Global Min-Cut in Undirected Graphs

Lecture from: 15.05.2025 | Video: Homelab | Rui Zhangs Notes

In this lecture, we study the classic global Minimum Cut (MIN-CUT) problem in undirected multigraphs. We explore a powerful randomized algorithm based on edge contractions - a method that is conceptually simple, easy to implement, and surprisingly effective. By carefully analyzing the probability of preserving a minimum cut, we obtain efficient Monte Carlo algorithms whose success probability can be amplified. We conclude with an improved version using recursive contraction to optimize runtime further.

Problem Definition

The Global Min-Cut Problem

Let $G=(V,E)$ be an undirected multigraph (i.e., multiple edges between the same pair of vertices are allowed, but no self-loops).

A cut in $G$ is a subset of edges $C\subseteq E$ such that removing all edges in $C$ disconnects the graph. That is, the graph $(V,E\setminus C)$ becomes disconnected.

The minimum cut of $G$, denoted $\mu (G)$, is defined as:

Alternatively, one can think of cuts as induced by partitions $(S,T)$ of $V$, where:

• $S\cup T=V$, $S\cap T=\varnothing$
• The cut-set $C(S,T)\subseteq E$ consists of all edges with one endpoint in $S$ and the other in $T$
• Then, $\mu (G)={\min }_{S\subset V}|C(S,V\setminus S)|$

This problem is of central importance in network reliability, graph connectivity, and clustering.

Observations and First Approach

Let’s begin with a few basic facts.

• If $G$ is disconnected, then $\mu (G)=0$
• For connected $G$, the following bound always holds:

This makes sense: removing all edges incident to a single vertex will disconnect it from the rest of the graph.

Using Max-Flow Algorithms

We can compute minimum s-t cuts efficiently (e.g., via Ford-Fulkerson or push-relabel). To find a global min-cut, we can compute $n-1$ s-t min-cuts:

• Fix a source vertex $s$
• For every other vertex $t\in V\setminus \{s\}$, compute min-cut between $s$ and $t$

This results in $O(n)$ flow computations.

• Each computation takes $O(mn\log n)$ in best known implementations
• Total time: $O(n^{2}m\log n)=O(n^4\log n)$

This becomes the benchmark we aim to beat.

Why can we fix $s$?

The reason we can fix a single node $s$ and compute the minimum $s$-$t$ cut for all other nodes $t\in V\setminus \{s\}$ is due to the submodularity and symmetry of cuts in undirected graphs:

Any global minimum cut must separate some pair of nodes. So, by computing the minimum cut between one fixed node $s$ and all others, we are guaranteed to find at least one of the minimum cuts of the graph.

This works because the smallest cut found among all $s$-$t$ cuts (for fixed $s$) is equal to the global minimum cut. You don’t need to try all $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ pairs - the worst-case cut is always revealed by some $s$-$t$ pair involving any fixed $s$.

Randomized Algorithm via Edge Contraction

Edge Contraction Operation

Given an undirected multigraph $G=(V,E)$, and an edge $e=\{u,v\}\in E$, the contraction of $e$ merges vertices $u$ and $v$ into a new vertex $x_{u,v}$. All edges incident to $u$ or $v$ now attach to $x_{u,v}$, and any parallel edges are preserved (multiple edges between same pairs allowed).

• Any loops formed are discarded
• The number of vertices decreases by 1

Why Contracting Makes Sense

Let’s denote the contracted graph as $G/e$. If a minimum cut $C$ does not use edge $e$, then $C$ is still a cut in $G/e$, and:

However, in general:

That is, contraction cannot make the minimum cut value smaller. It either increases or preserves it.

Lemma: Cut Value Monotonicity under Contraction

Let $e\in E$. Then:

• $\mu (G/e)\ge \mu (G)$
• If $e\notin C$ for some minimum cut $C$, then $\mu (G/e)=\mu (G)$

This motivates selecting edges not in the minimum cut. But we don’t know the cut yet - so we pick edges randomly and hope not to hit the critical ones.

The Random Contraction Algorithm

Cut(G):
    while |V(G)| > 2:
        choose edge e ∈ E uniformly at random
        G ← G/e
    return size of the cut formed by the remaining two vertices

This process leaves exactly two supernodes, and the set of edges between them corresponds to some cut in the original graph.

Key Insight

If none of the minimum cut edges are contracted, then the final cut is a minimum cut. So what is the probability that this happens?

Let $\mu =\mu (G)$, and suppose $C$ is a minimum cut of size $\mu$. Then:

• Each vertex has degree at least $\mu$
• Total number of edges $|E|\ge \frac{n\mu }{2}$

Thus, the probability that a randomly chosen edge is in the cut is at most:

So:

This means with each contraction, the chance of not destroying the minimum cut is reasonably high.

Total Success Probability

Let $\hat{p}(n)$ be the worst-case success probability for a graph with $n$ vertices. Then:

Iterating this recurrence yields:

Thus, the success probability is small - only $\approx \frac{1}{n^2}$ - but not negligible, and we can amplify it.

Amplifying Success Probability

Run the algorithm $\lambda \cdot \left(\genfrac{}{}{0ex}{}{n}{2}\right)$ times. Output the smallest cut found. Then:

• With probability at least $1-e^{-\lambda }$, the minimum cut is found
• For example, $\lambda =\ln n\Rightarrow$ success probability $\ge 1-\frac{1}{n}$

Each run takes $O(n^2)$ time (assuming naive edge lists). Total time:

Improved Version: Karger-Stein Algorithm (Bootstrapping)

Let’s reduce the number of contraction steps by stopping early - say, when the graph has $t$ vertices left.

Then:

• Run the contraction process until $t$ vertices remain
• Recursively apply the min-cut algorithm on the smaller graph

This reduces the chance of killing the minimum cut, especially in the later stages.

Runtime Analysis

Let $t=\sqrt{n}$. Then the runtime is:

Repeating $O(n^2)$ times still gives $O(n^3\log n)$ time overall.

Final Result

This recursive bootstrapped approach leads to a runtime of:

and is known as the Karger-Stein algorithm.

Summary

When we don’t know what the minimum cut is, the best we can do is to avoid breaking it - and with luck, that’s enough.

Continue here: 24 Smallest Enclosing Disk via Randomized Algorithms