Karger–Klein–Tarjan Randomized Minimum Spanning Tree Algorithm

Karger–Klein–Tarjan randomized minimum spanning tree algorithm (commonly abbreviated as the KKT algorithm) is a Las Vegas randomized comparison-based graph algorithm in computation and algorithms published by David R. Karger, Philip N. Klein, and Robert E. Tarjan in 1995 (Journal of the ACM) that computes the minimum spanning tree (or minimum spanning forest) of an arbitrary undirected edge-weighted graph G = (V, E) with n = |V| vertices and m = |E| edges in O(m + n) expected time and O(m + n) worst-case space. Operating in the pointer-machine comparison model—where edge weights are arbitrary real numbers accessed through pairwise order comparisons (w(e₁) < w(e₂)) without integer bit manipulation or radix addressing—the KKT algorithm resolved a decades-old open question in algorithmic graph theory by proving that minimum spanning forests can be constructed in linear expected time using only weight comparisons. The algorithm interleaves three structural mechanisms: deterministic vertex-set reduction via two rounds of Borůvka's algorithm, independent Bernoulli random edge sampling at probability p = 1/2 to construct a sparse subgraph H, and deterministic linear-time MST verification (Dixon, Rauch, and Tarjan, 1992; King, 1995) to discard edges heavier than the bottleneck path connecting their endpoints in the minimum spanning forest of H.

The Comparison-Based Minimum Spanning Tree Barrier

Let G = (V, E) be an undirected graph with n vertices, m edges, and an injective weight function w : E → ℝ assigning distinct real weights to all edges (ties among equal weights can be broken deterministically by lexicographic vertex-pair indexing). If G is disconnected, the objective is to compute the minimum spanning forest F*(G), defined as the union of the minimum spanning trees of each connected component of G.

For nearly seventy years following Otakar Borůvka's 1926 algorithm, every comparison-based method for constructing F*(G) incurred superlinear overhead on sparse or moderately dense graphs due to priority-queue maintenance or global edge sorting:

• Borůvka's algorithm (1926): Executes up to ⌈log₂ n⌉ parallel minimum-incident-edge contraction phases in O(m log n) deterministic time.
• Kruskal's algorithm (1956): Sorts all m edges in O(m log n) comparisons and scans them with a disjoint-set data structure in O(m α(m, n)) overhead.
• Prim's algorithm (1957) with Fibonacci heaps (Fredman and Tarjan, 1987): Achieves O(m + n log n) time, which is linear only when m = Ω(n log n).
• Packetized Fibonacci-heap contractions (Fredman and Tarjan, 1987; Gabow, Galil, Spencer, and Tarjan, 1986): Reduced deterministic comparison complexity first to O(m β(m, n)) and subsequently to O(m log β(m, n)), where β(m, n) = min{i ≥ 1 : log⁽ⁱ⁾ n ≤ m/n}.

In 1990, Michael L. Fredman and Dan E. Willard bypassed the comparison model by introducing fusion trees and the atomic heap on the transdichotomous Word RAM, achieving O(m + n) deterministic time for integer edge weights via word-level multiplication and bit-packing. However, whether O(m + n) complexity was achievable in the comparison decision-tree model remained open until Karger (1993) observed that random edge sampling combined with cycle-property filtering could thin dense graphs, which Karger, Klein, and Tarjan (1995) refined into a recursive linear-expected-time algorithm.

Cut and Cycle Duality Principles

The correctness and filtering mechanics of the KKT algorithm rest on the dual optimality conditions characterizing F*(G) (Tarjan, 1983):

1. The Cut Property (Blue Rule): For any subset of vertices S ⊆ V, the minimum-weight edge with one endpoint in S and the other in V \ S belongs to F*(G). Contracting any forest of minimum-incident edges preserves the identity of all remaining edges of F*(G).
2. The Cycle Property (Red Rule): For any cycle C in G, the heaviest edge on C does not belong to F*(G). Equivalently, for any forest F ⊆ E and any edge e = (u, v) ∈ E, let P_F(u, v) denote the unique simple path between u and v in F when u and v lie in the same connected component of F. Define the bottleneck weight w_F(u, v) as the maximum weight w(e') along P_F(u, v), with w_F(u, v) = +∞ if u and v lie in different components of F. An edge e = (u, v) is called F-heavy if w(e) > w_F(u, v), and F-light if w(e) ≤ w_F(u, v). By the Cycle Property, no F-heavy edge can belong to F*(G), because e is the heaviest edge on the fundamental cycle P_F(u, v) ∪ {e}. Deleting all F-heavy edges from G therefore leaves a sparser subgraph containing every edge of F*(G).

The KKT algorithm achieves O(m + n) expected time by balancing vertex contraction against edge sparsification so that both Recursive Call 1 (on a random sample) and Recursive Call 2 (on the surviving F-light edges) operate on graphs with geometrically smaller vertex counts and bounded expected edge counts.

1. Borůvka Contraction Steps (Vertex Reduction)

Given an input graph G with n vertices and m edges, a single Borůvka step operates as follows:

1. For each non-isolated vertex v ∈ V, scan its adjacency list to identify its minimum-weight incident edge e_min(v).
2. Add the collection of selected edges B = {e_min(v) : v ∈ V} to the output minimum spanning forest. Because weights are distinct, B contains no cycles and forms a forest.
3. Contract each connected component of (V, B) into a single supervertex using depth-first search, removing self-loops (u, u) and discarding redundant parallel edges between the same pair of supervertices by keeping only the minimum-weight edge.

Every non-isolated vertex joins a connected component of size at least 2 during one Borůvka step, halving the number of vertices. Executing two consecutive Borůvka steps takes O(m + n) deterministic time and reduces the number of surviving vertices to at most:

While Borůvka steps reduce the vertex count by a factor of 4, they are not guaranteed to reduce the edge count m by a constant factor on dense graphs. To reduce m simultaneously, the KKT algorithm applies random edge sampling.

2. Random Edge Sampling and the Random Sampling Lemma

After two Borůvka steps produce a contracted graph G' = (V', E') with n' ≤ n/4 vertices and m' ≤ m edges, the algorithm constructs a random subgraph H = (V', E_H) by independently including each edge e ∈ E' in E_H with probability p = 1/2. The expected number of edges in H is E[|E_H|] = m' / 2 ≤ m / 2. The algorithm then makes Recursive Call 1 on H to compute its minimum spanning forest F = F*(H).

The Random Sampling Lemma of Karger, Klein, and Tarjan proves that F = F*(H) is so close to F*(G') that the expected number of F-light edges in G' is at most n' / p = 2n' ≤ n / 2—independent of m'!

Proof of the Random Sampling Lemma (Deferred Coin-Flip Argument)

Lemma (Karger, Klein, and Tarjan, 1995): Let G' = (V', E') be any weighted graph on n' vertices, let H be obtained by sampling each edge of E' independently with probability p ∈ (0, 1), and let F = F*(H) be the minimum spanning forest of H. Then the number of F-light edges in E' is stochastically dominated by a negative binomial distribution with parameters n' − 1 and p, and its expectation is at most (n' − 1) / p < n' / p.

Proof: Sort all edges of E' in increasing order of weight: e₁, e₂, …, e_m' with w(e₁) < w(e₂) < ⋯ < w(e_m'). Recall that Kruskal's algorithm constructs F = F*(H) by scanning the sampled edges in increasing order of weight and adding e_i ∈ H to F if and only if its endpoints lie in different connected components of the forest F_i−1 constructed from {e₁, …, e_i−1} ∩ H.

Using the principle of deferred decisions, scan e₁, e₂, …, e_m' one edge at a time and flip the coin for e_i = (u_i, v_i) only when needed:

1. Case A (u_i and v_i are already connected in F_i−1): Every edge on the path between u_i and v_i in F_i−1 precedes e_i in the sorted order and has weight less than w(e_i). Thus w(e_i) > w_F(u_i, v_i), so e_i is F-heavy regardless of its coin toss, and Kruskal's algorithm on H rejects e_i even if sampled.
2. Case B (u_i and v_i lie in different components of F_i−1): No path in F_i−1 connects u_i and v_i, so e_i is F-light. Now flip the coin for e_i (heads with probability p, tails with probability 1 − p). If the coin lands heads, e_i enters H and is added to F_i−1 by Kruskal's algorithm, increasing |F| by 1. If the coin lands tails, e_i is not in H (F_i = F_i−1), but still counts as an F-light edge of G'.

Because any forest F on n' vertices contains at most n' − 1 edges, Case B can produce at most n' − 1 heads across the entire scan. Every F-light edge corresponds to a trial in Case B before the (n' − 1)-th head. The expected number of Bernoulli(p) trials required to achieve n' − 1 heads is (n' − 1) / p. For p = 1/2, the expected number of F-light edges in G' is at most 2(n' − 1) < 2n'.

3. Linear-Time MST Verification and Heavy-Edge Filtering

Once Recursive Call 1 returns the minimum spanning forest F of H, the algorithm must identify and delete all F-heavy edges in G', retaining only E_light = {e = (u, v) ∈ E' : w(e) ≤ w_F(u, v)}. This is the MST verification problem (tree path-maxima query problem). While Robert E. Tarjan (1979) answered offline path-maxima queries in O(m' α(m', n')) comparisons via path compression, the KKT algorithm achieves linear O(m' + n') deterministic time using the verification algorithm of Brandon Dixon, Monika Rauch, and Robert E. Tarjan (1992), simplified by Valerie King (1995) and Torben Hagerup (2009):

1. Conversion to Full Branching Borůvka Tree (King, 1995): Run Borůvka's algorithm on the tree F in O(n') time and record the component-merge hierarchy as a rooted branching tree B_F of height at most ⌈log₂ n'⌉ with n' leaves. King proved that for any pair of vertices u, v ∈ V', the bottleneck path weight w_F(u, v) in F equals the maximum edge weight on the unique path between leaves u and v in B_F.
2. Lowest Common Ancestor (LCA) and Micro-Tree Decomposition: Using linear-time Gabow–Tarjan LCA preprocessing on B_F, split each query (u, v) into two ancestor-descendant path-maxima queries (a, u) and (a, v) where a = LCA(u, v), and evaluate them in O(m' + n') comparisons via Komlós's (1985) downward bit-vector stack algorithm and small micro-tree lookup tables.

After deleting all F-heavy edges in O(m' + n') time, the algorithm makes Recursive Call 2 on G_light = (V', E_light), which has n' ≤ n/4 vertices and expected edge count E[|E_light|] < 2n' ≤ n/2.

Recursive Procedure

Given an undirected weighted graph G = (V, E) with n vertices and m edges:

1. Base Case: If E = ∅, return ∅.
2. Step 1 (Borůvka Contraction): Execute two Borůvka phases on G, collecting the contracted edges into F₀ and producing G' = (V', E') with n' ≤ n/4 vertices and m' ≤ m edges.
3. Step 2 (Random Sampling): Form H = (V', E_H) by sampling each edge e ∈ E' independently with probability p = 1/2.
4. Step 3 (Recursive Call 1): Compute F = KKT(H), the minimum spanning forest of H.
5. Step 4 (Verification Filtering): Run linear-time MST verification on (G', F) to extract the F-light edge set E_light = {e = (u, v) ∈ E' : w(e) ≤ w_F(u, v)}.
6. Step 5 (Recursive Call 2): Compute F' = KKT(V', E_light) and return F₀ ∪ F'.

Solution of the Stochastic Recurrence

Let T(m, n) denote the expected number of comparisons and pointer operations on a graph with m edges and n vertices. Combining the deterministic O(m + n) work of Steps 1, 2, and 4 with the two recursive calls gives:

Viewing the recursion as a binary tree where every node at depth d ≥ 0 has at most n_d ≤ n / 4^d vertices:

• Vertex Work Across Depth d: Across all 2^d recursion nodes at depth d, the sum of vertex counts is at most 2^d · (n / 4^d) = n / 2^d, which sums over d ≥ 0 to 2n = O(n).
• Edge Work Along Left and Right Branches: Along the root's left branch (sampling), expected edge counts halve at each step (m → m/2 → m/4), summing to 2m. Whenever a node at depth d branches right (filtering), its child receives at most 2n_d+1 ≤ n / (2 · 4^d) edges in expectation, and its subsequent left-branch chain sums to at most n / 4^d edges. Summing over all 2^d nodes at depth d yields ∑_d≥0 2^d (n / 4^d) = 2n.

Thus E[T(m, n)] ≤ 2c(m + n) = O(m + n). Moreover, by negative binomial tail concentration across the recursion tree, the running time is O(m + n) with high probability 1 − e^−Ω(m).

Is the Karger–Klein–Tarjan algorithm a Monte Carlo or a Las Vegas randomized algorithm?

The KKT algorithm is a Las Vegas algorithm: it always outputs the true minimum spanning forest and never errs. Randomness is used only in Step 2 to select a sparse subgraph H with probability p = 1/2 so that its spanning forest F filters out F-heavy edges. Because every discarded edge is certified by the deterministic Cycle Property to be heavier than the fundamental cycle it forms with F, no edge of the true minimum spanning forest is ever discarded.

Why are two Borůvka steps required before each random sampling phase?

If only one Borůvka step were executed per phase, the vertex count would drop by a factor of 2 (n' ≤ n/2) while spawning 2 recursive calls, causing the 2^d subproblems at depth d to sum to Θ(n) vertices per level across log₂ n levels (O(m + n log n) time). Executing two Borůvka steps reduces the vertex count to at most n/4 while making 2 recursive calls, so total vertex work at depth d decays geometrically as 2^d · (n / 4^d) = n / 2^d and sums to O(n).

Why does the Random Sampling Lemma bound the number of F-light edges by 2n regardless of m?

When scanning all edges of G' in increasing weight order, an edge e is F-light if and only if its endpoints lie in different connected components of the sampled forest F constructed so far. Each such edge is included in H (and added to F) with probability p = 1/2. Because F is an acyclic forest on n' vertices, it can accept at most n' − 1 edges before spanning all components. Waiting for at most n' − 1 heads from a fair coin (p = 1/2) takes at most 2(n' − 1) < 2n' trials in expectation, regardless of m'.

1. Karger, D. R., Klein, P. N., & Tarjan, R. E. (1995). A randomized linear-time algorithm to find minimum spanning trees. Journal of the ACM, 42(2), 321–328. https://doi.org/10.1145/201019.201022
2. Dixon, B., Rauch, M., & Tarjan, R. E. (1992). Verification and sensitivity analysis of minimum spanning trees in linear time. SIAM Journal on Computing, 21(6), 1184–1192. https://doi.org/10.1137/0221070
3. King, V. (1995). A simpler minimum spanning tree verification algorithm. Algorithmica, 18(2), 263–270. https://doi.org/10.1007/BF02523171
4. Pettie, S., & Ramachandran, V. (2002). An optimal minimum spanning tree algorithm. Journal of the ACM, 49(1), 16–34. https://doi.org/10.1145/505241.505243
5. King, V. (1997). A simpler minimum spanning tree verification algorithm. Algorithmica, 18(2), 263–270. https://doi.org/10.1007/BF02523171