Randomized Min-Cut: Karger's Algorithm for Graph Cuts Explained with Examples

Randomized Min-Cut: Karger’s Algorithm for Graph Cuts is a powerful probabilistic technique designed to find a minimum cut in an undirected graph. Unlike deterministic approaches, Karger’s algorithm uses random edge contractions to efficiently approximate solutions for the minimum cut problem with high probability.

Table of Contents

What is the Min-Cut Problem in Graph Theory?

The minimum cut of a graph is the smallest set of edges that, if removed, partition the graph into two disconnected subgraphs. Finding this min-cut is fundamental in network reliability, image segmentation, clustering, and many optimization problems in computer science.

The challenge is that the min-cut problem can be computationally expensive for large graphs. Karger’s algorithm introduces a randomized approach that simplifies this while maintaining reasonable accuracy with repeated trials.

Overview of Karger’s Randomized Min-Cut Algorithm

Karger’s algorithm repeatedly contracts random edges between vertices, merging them until only two vertices (supernodes) remain. The edges between these two supernodes represent a cut, and the one with the minimum edges after multiple iterations tends to be the global min-cut.

Algorithm Steps:

Start with a connected, undirected graph G.
Randomly select an edge and contract it, merging its vertices into one, replacing the vertices with a supernode.
Remove any self-loops created by this contraction.
Repeat contraction until only two vertices remain.
The edges connecting these two vertices form a cut; record its size.
Repeat the entire process multiple times to increase the probability of finding the true minimum cut.

Why Use Randomization?

The core concept is that a random edge contraction avoids bias and explores many possible partitions. Probability theory shows that repeating the algorithm enough times (about \(O(n^2 \log n)\) where \(n\) is the number of vertices) provides a high likelihood of retrieving the true min-cut.

Example Walkthrough

Consider the following simple graph with 4 vertices and 5 edges:

Step-by-step:

Randomly pick an edge, say (B, D), and contract to form supernode BD.
Remove self-loops, if any.
New graph now has vertices: A, BD, C.
Repeat: contract edge (C, BD) to form supernode BDC.
New graph has vertices: A, BDC.
The edges between A and BDC define a cut.

This yields a cut between vertex A and supernode BDC. The number of edges crossing this cut is the min-cut candidate for this run.

Interactive Visual Demonstration (Concept)

An interactive tool would allow users to:

Input or draw a graph.
Step through random edge contractions with visual highlights.
Observe how edges disappear and supernodes form.
See the final two supernodes and their crossing edges representing the min-cut.

This can help build intuition for the random contraction process and the probabilistic nature of the algorithm.

Algorithm Complexity and Performance

Karger’s algorithm is simple and elegant but needs multiple executions for high confidence. Each contraction step can be done in \(O(1)\) with proper data structures, and the entire process takes \(O(n^2)\) time per run. Running it \(O(n^2 \log n)\) times yields a high probability of success.

Code Example in Python

import random
from copy import deepcopy

def karger_min_cut(graph):
    # graph: {node: set(connected nodes)}
    g = deepcopy(graph)
    while len(g) > 2:
        u = random.choice(list(g.keys()))
        v = random.choice(list(g[u]))
        # Contract edge u-v
        # Merge v into u
        g[u].update(g[v])
        g[u].discard(u)
        g[u].discard(v)
        for node in g[v]:
            g[node].discard(v)
            g[node].add(u)
        del g[v]

    # Remaining edges represent the cut
    nodes = list(g.keys())
    return len(g[nodes[0]])

# Example graph as adjacency sets
graph = {
    'A': {'B', 'D', 'C'},
    'B': {'A', 'C', 'D'},
    'C': {'A', 'B', 'D'},
    'D': {'A', 'B', 'C'}
}

# Run multiple times to increase accuracy
min_cut = min(karger_min_cut(graph) for _ in range(100))
print("Minimum cut found:", min_cut)

Summary

Karger’s randomized min-cut algorithm is an elegant solution to an otherwise computationally intensive problem. By intelligently using randomness and edge contractions, it finds a minimum cut with a high probability after multiple iterations. Combining theoretical understanding with visual examples and code helps deepen the grasp of this fundamental graph algorithm.