A Tutorial on the Karger Algorithm for Minimum Cut

A graph can represent roads between suburbs, links between web pages, or communication channels between computers. A cut divides the graph’s vertices into two non-empty groups, and its capacity is the number of edges crossing between those groups. The minimum cut is the smallest such boundary. Finding it is useful when studying network reliability: removing every edge in a minimum cut disconnects the system as cheaply as possible.

The Karger algorithm for minimum cut takes a deliberately random approach. Instead of examining every possible division of the vertices, it repeatedly contracts randomly selected edges until only two supervertices remain. The edges between those final supervertices form a candidate cut. Randomness means a single run can miss the optimum, but many independent runs make the probability of finding the true answer high.

This method is especially useful as a teaching algorithm because its central operation is easy to visualise and its probability analysis reveals an important idea in randomized algorithms. A graph of Melbourne tram connections, Sydney ferry links, or a small network used in a university practical can all provide an intuitive example. The algorithm is simple enough to implement in Python, C, or pseudocode, while still raising practical questions about efficiency and data representation.

What A Minimum Cut Represents

Let an undirected graph be written as (G=(V,E)), where (V) is the set of vertices and (E) is the set of edges. A partition divides (V) into two groups, (S) and (V-S). The cut-set contains every edge with one endpoint in each group. The size of that set is the cut value. The global minimum cut is the smallest cut value over every valid partition.

For example, consider a network with vertices representing data centres in Brisbane, Perth, and Canberra. If only two links connect one cluster of centres to the rest of the graph, the corresponding cut has value two. Those links are a possible vulnerability: losing both could isolate the cluster. This interpretation applies to physical infrastructure, distributed systems, and graph-based clustering.

The algorithm assumes an undirected multigraph. A multigraph can contain parallel edges between the same pair of vertices, which is essential after contractions. A self-loop, where an edge connects a supervertex to itself, never crosses a partition and must be removed. If the input is already disconnected, the minimum cut is zero, so that case can be handled before running random trials.

The Contraction Procedure

Karger’s method starts with every original vertex as its own supervertex. It then selects an edge uniformly at random and contracts it. If the selected edge joins (u) and (v), the two vertices become one supervertex. Every edge formerly incident to (u) or (v) is redirected to the merged vertex. Self-loops are deleted, while parallel edges remain as separate entries.

The process continues until exactly two supervertices remain. All surviving edges must run between those two groups, so their count is a cut candidate. The graph should be copied before each trial because contraction destroys the current representation. The best candidate over all trials is returned as the algorithm’s answer.

A compact version of the procedure looks like this:

• Copy the original undirected multigraph.
• While more than two supervertices remain, choose a random edge.
• Merge its two endpoint supervertices.
• Remove self-loops and preserve parallel edges.
• Count the remaining crossing edges and update the best result.

The random choice must be made from edges that still exist after previous contractions. Choosing from the original edge list without checking could select a deleted self-loop or an invalid endpoint. In a small educational implementation, an edge list plus a component label for each original vertex is usually clearer than a sophisticated disjoint-set structure.

Why Repetition Makes It Reliable

Suppose the graph has (n) vertices and the unknown minimum cut has (k) edges. At an intermediate stage with (r) supervertices, every supervertex has degree at least (k), so the graph contains at least (rk/2) edges. The probability of selecting an edge from the target minimum cut is therefore at most (k/(rk/2)=2/r).

The chance of avoiding the target cut while reducing the graph from (n) to two supervertices is at least

[ \frac{n-2}{n}\cdot\frac{n-3}{n-1}\cdots\frac{2}{3} = \frac{2}{n(n-1)}. ]

This is the success probability of one trial. It becomes small as the graph grows, but independent repetition changes the picture. If one run succeeds with probability (p), then (t) runs fail with probability at most ((1-p)^t), which is approximately (e^{-pt}). To obtain a fixed confidence level, the basic algorithm generally needs on the order of (n^2\log n) trials.

That cost is the trade-off for simplicity. Karger’s algorithm is valuable for understanding randomised analysis, yet a direct implementation may be too slow for a large production graph. Karger–Stein improves the probability using recursive contraction, and deterministic flow-based methods may be preferable when an exact answer must be obtained quickly and predictably.

Implementing It With An Edge List

An edge list stores each edge as a pair such as ((u,v)). During contraction, choose an edge, replace every occurrence of one endpoint with the other, and filter out pairs whose two endpoints are now equal. Parallel pairs are intentionally retained. If the graph has (m) edges and a trial performs (n-2) contractions, repeatedly scanning the full edge list can cost roughly (O(mn)) time for that trial.

A component map makes the final count straightforward. Initially, each vertex maps to itself. When (u) is merged into (v), every original vertex currently belonging to (u)’s component is reassigned to (v). At the end, count original edges whose endpoints have different component labels. This avoids confusing the number of original vertices with the number of current supervertices.

A practical Python-style pseudocode implementation is:

karger_trial(edges, vertices):
    current_edges = copy(edges)
    groups = {v: v for v in vertices}
    remaining = set(vertices)

    while size(remaining) > 2:
        (a, b) = random choice from current_edges
        keep = a
        remove = b

        for v in vertices:
            if groups[v] == remove:
                groups[v] = keep

        remaining.remove(remove)

        current_edges = [
            (x, y) after replacing remove by keep
            for (x, y) in current_edges
            if x != y after replacement
        ]

    return length(current_edges)

The pseudocode assumes that edge endpoints are supervertex labels. A real implementation should canonicalise undirected edges where useful, seed or control its random generator during testing, and avoid mutating the caller’s input. Readers practising graph problems can compare this implementation style with other algorithmic patterns in problem-solving practice.

Choosing Data Structures And Checking Results

For small graphs, an edge list is transparent and easy to debug. An adjacency list can make neighbourhood operations more natural, but contraction requires careful updates to both endpoint lists and duplicate edges. An adjacency matrix is convenient for dense graphs, although selecting a uniformly random existing edge can require scanning many matrix entries.

A disjoint-set union structure, also called union-find, can track which original vertices belong to each supervertex. It is excellent for connectivity queries and supports near-constant amortised union operations. However, it does not remove edges by itself. The implementation still needs a strategy for sampling active edges and ignoring self-loops.

Useful checks should be performed before trusting the output:

• Confirm that the graph is undirected and has no invalid vertex labels.
• Verify that contractions preserve parallel edges.
• Test a triangle, whose minimum cut is two.
• Test a graph with a bridge, whose minimum cut is one.
• Run many trials and compare the smallest answer with a trusted method.
• Check a disconnected graph separately and return zero.

A triangle is a particularly good first test because every pair of vertices has one edge and every non-trivial partition cuts two edges. A square with a diagonal tests parallel-edge handling after contraction. For a larger test, generate a connected random graph and compare repeated Karger trials with a brute-force partition search while the vertex count is still small.

Complexity, Extensions, And Practical Use

Let (n=|V|) and (m=|E|). With a straightforward edge-list implementation, one trial commonly takes (O(mn)) time, and (O(n^2\log n)) repetitions can make the total cost approximately (O(mn^3\log n)). The exact bound depends on how components, active edges, and random selection are represented. Space usage is usually (O(n+m)) for the graph and bookkeeping.

The algorithm can be adapted to weighted graphs by treating an edge of weight (w) as (w) parallel edges when weights are small integers. For larger weights, select edges with probability proportional to their weights instead. The cut value then becomes the sum of crossing weights. Care is needed with floating-point sampling and with zero-weight edges, which should not distort the probability distribution.

Karger’s idea also fits broader network-analysis work. It can provide a quick exploratory estimate of a sparse graph’s weakest separation before a more advanced algorithm is applied. In Australian research groups and software teams, where cloud and data-centre costs can make repeated computation worth measuring, profiling the contraction loop matters as much as writing correct pseudocode. A clear implementation helps explain why an elegant randomised method may still need optimisation for large inputs.

The method belongs alongside other graph techniques rather than replacing them all. Maximum-flow algorithms can find a minimum (s)-(t) cut for specified source and sink vertices, while a global minimum cut asks for the best separation over every possible pair of sides. Understanding that distinction prevents a common mistake: solving a related flow problem and assuming it answers the global question.

Common Mistakes And A Learning Path

The most frequent error is deleting parallel edges after a contraction. Two edges that become identical still represent two distinct original connections, so removing one can reduce the apparent cut incorrectly. Another error is counting self-loops in the final answer. A self-loop lies entirely inside one side of every partition and contributes nothing.

It is also easy to report one trial’s result as if it were guaranteed. The basic algorithm is probabilistic: a larger number of independent trials increases confidence but does not make the guarantee absolute. For a classroom demonstration, print the best value after batches of trials and observe whether it stabilises. For a service with strict correctness requirements, use a deterministic verification method or a more appropriate exact algorithm.

When explaining the algorithm to others, draw the supervertices after each contraction. Label each supervertex with the original vertices it contains, such as ({A,C}). Then the final two labels directly show the partition, and the remaining parallel edges show its capacity. This visual approach works well in a Melbourne study group, a Brisbane coding club, or an Australian university algorithms class because it connects the abstract operation to a concrete network.

A sensible learning sequence is to implement a brute-force minimum cut for tiny graphs, build the single-trial contraction routine, add repeated trials, and then measure runtime. Readers interested in probabilistic classifiers can also see how algorithm explanations differ across fields in this Naive Bayes guide. The shared lesson is to separate the mathematical guarantee, the implementation details, and the limits of the method being used.