Karger's Randomized Min-Cut Algorithm

Why the Min-Cut Problem Matters

The minimum cut problem asks: what is the smallest set of edges that, if removed, disconnects a graph? This seemingly theoretical question has profound real-world applications in network reliability, clustering, circuit design, and image segmentation.

Why this matters for your career:

• Min-cut is fundamental to network reliability analysis
• Used in image segmentation (graph cut algorithms are standard in computer vision)
• Understanding Karger's algorithm demonstrates mastery of randomized algorithms
• The algorithm is elegantly simple — only 15 lines of code — yet mathematically deep

What Is Karger's Algorithm?

Karger's algorithm, published by David Karger in 1993, is a randomized algorithm that finds the minimum cut in a graph. The algorithm works by repeatedly contracting random edges until only two vertices remain — the edges between them form a candidate cut.

Edge Contraction

Contracting an edge (u, v) means:

1. Merge vertices u and v into a single super-vertex uv
2. Remove self-loops (edges from uv to itself)
3. Keep all other edges (parallel edges are merged, not removed)

The contraction operation reduces the graph size by one vertex.

The Algorithm

import random
import copy


def karger_min_cut(graph):
    """
    Karger's randomized algorithm for minimum cut.
    graph: dict where graph[u] = [(v, weight), ...]
    Returns the size of the cut (total weight of edges crossing the cut).
    """
    # Make a working copy
    vertices = set(graph.keys())
    edges = {}
    for u in graph:
        for v, w in graph[u]:
            if u < v:
                edges[(u, v)] = w
            else:
                edges[(v, u)] = w

    # While more than 2 vertices remain
    while len(vertices) > 2:
        # Choose a random edge
        edge = random.choice(list(edges.keys()))
        u, v = edge

        # Contract u and v into a super-vertex
        # Let's say u absorbs v
        vertices.remove(v)

        # Redirect all edges from v to u
        new_edges = {}
        for (a, b), w in edges.items():
            if a == v:
                a = u
            if b == v:
                b = u
            if a != b:
                if a < b:
                    new_edges[(a, b)] = new_edges.get((a, b), 0) + w
                else:
                    new_edges[(b, a)] = new_edges.get((b, a), 0) + w

        edges = new_edges

    # The remaining edges form the cut
    return sum(edges.values())


def karger_with_iterations(graph, iterations):
    """Run Karger's algorithm multiple times and return the best cut."""
    best_cut = float('inf')

    for i in range(iterations):
        cut_size = karger_min_cut(graph)
        if cut_size < best_cut:
            best_cut = cut_size
            print(f"Iteration {i+1}: new best cut = {cut_size}")

    return best_cut

Example

Consider a simple graph with 4 vertices:

A -- B   (weight 1)
A -- C   (weight 2)
A -- D   (weight 3)
B -- C   (weight 1)
C -- D   (weight 1)

The minimum cut is 1 (the edge A-B or B-C or C-D).

graph = {
    'A': [('B', 1), ('C', 2), ('D', 3)],
    'B': [('A', 1), ('C', 1)],
    'C': [('A', 2), ('B', 1), ('D', 1)],
    'D': [('A', 3), ('C', 1)]
}

result = karger_with_iterations(graph, 50)
print(f"Minimum cut: {result}")
# Output: Minimum cut: 1

Why Randomization Works

The key insight is that the minimum cut is unlikely to be contracted. If the minimum cut has size c and the total edge weight is E, any given edge has probability roughly c/E of being in the min cut. Since the min cut is small by definition, it is unlikely that any of its edges are contracted.

Success Probability

• A single run succeeds with probability at least 2/(n*(n-1))
• After n*(n-1)/2 * ln(n) runs, the probability of failure is ≤ 1/n

| Graph Size (n) | Single Run Success | Runs for 95% Confidence | |----------------|-------------------|------------------------| | 10 | ~2.2% | ~135 | | 100 | ~0.02% | ~23,000 | | 1,000 | ~0.0002% | ~3,450,000 | | 10,000 | ~0.000002% | ~460,000,000 |

This is why we must run Karger's algorithm many times and take the best result.

Comparison with Other Min-Cut Algorithms

| Algorithm | Type | Complexity | Deterministic | |-----------|------|------------|--------------| | Karger's | Randomized | O(n^2 * log n) expected | No | | Stoer-Wagner | Deterministic | O(n * m log n) | Yes | | Max-flow min-cut (Dinic) | Deterministic | O(m * sqrt(n)) for unit capacities | Yes | | Edmonds-Karp | Deterministic | O(V * E^2) | Yes |

Karger's algorithm is simpler to implement but needs multiple runs. Stoer-Wagner is the fastest deterministic global min-cut algorithm.

Real-World Applications

| Application | How Min-Cut Is Used | |-------------|---------------------| | Network Reliability | Find the weakest link in a communication network | | Image Segmentation | Cut an image into foreground and background regions | | Clustering | Partition data points into meaningful groups | | Circuit Design | Find critical connections in electronic circuits | | Social Network Analysis | Identify community boundaries | | Supply Chain | Find vulnerabilities in logistics networks | | VLSI Design | Partition circuits onto chips |

Improvements: Karger-Stein Algorithm

Karger and Stein improved the original algorithm by noting that as the graph shrinks, the success probability of each subsequent contraction increases. Their improved version:

1. Contract until n/sqrt(2) vertices remain
2. Recurse twice on the resulting graph
3. Return the better of the two results

This gives O(n^2 * log^3 n) expected time — a significant improvement.

Summary

Karger's randomized min-cut algorithm is beautiful in its simplicity: repeatedly contract random edges until two vertices remain. The minimum cut survives with surprising probability because it is small. Running the algorithm many times makes failure exponentially unlikely.

Key takeaways:

• Edge contraction merges two vertices, eliminating self-loops but keeping parallel edges
• A single run succeeds with probability ~2/n^2
• Running O(n^2 log n) times gives high confidence
• Karger-Stein improves complexity by recursive contraction
• Applications span network reliability, image segmentation, and clustering

What's Next: Probability Analysis

The next chapter covers probability analysis of randomized algorithms — using Chernoff bounds, Markov's inequality, and union bounds to prove algorithm performance.

Visualization of Edge Contraction

Step 0: Original graph (5 vertices)
    A --- B
    |     |
    C --- D --- E

Step 1: Contract edge (A, C)
    AC --- B
     |
     D --- E

Step 2: Contract edge (D, E)
    AC --- B
     |
     DE

Step 3: Contract edge (AC, B)
    ACB
     |
     DE

Result: 1 edge between ACB and DE — cut size is 1

Each contraction reduces vertex count by one. After n-2 contractions, only two super-vertices remain. The parallel edges between them accumulated throughout the process represent the total edge weight crossing the cut.

This visual intuition helps understand why the algorithm works — random contraction is unlikely to hit the small set of edges that form the minimum cut.