Chapter 8. The Minimum Spanning Tree Problem

Edge-inclusion lattices, the cut property, and three classical greedy algorithms recast as LLP forbidden/advance loops.

This page: LLP forms. View classical forms »

Setting

Given a connected, weighted, undirected graph $G = (V, E, w)$ with $n = |V|$ vertices and $m = |E|$ edges, a minimum spanning tree (MST) is a spanning tree $T \subseteq E$ that minimizes $\sum_{e \in T} w(e)$. When edge weights are distinct the MST is unique. The chapter develops three classical algorithms — Kruskal, Prim, Borůvka — each captured by a different greedy invariant on the same edge-inclusion lattice.

Key properties

Two structural lemmas drive every MST algorithm:

• Cut property. For any cut $(S, V \setminus S)$, the lightest crossing edge belongs to some MST. Prim's algorithm picks lightest edges out of a growing fragment; Borůvka grows multiple fragments concurrently.
• Cycle property. The heaviest edge of any cycle is excluded from every MST. Kruskal's algorithm processes edges in increasing weight order and rejects any that closes a cycle.

Kruskal's Algorithm

Sort edges in non-decreasing weight order. Maintain a union-find structure. Scan the sorted list: for each edge $(u, v)$, if $u$ and $v$ are in different components, accept the edge and merge the components; otherwise reject (it would close a cycle). Running time: $O(m \log n)$ dominated by the sort, plus $O(m \cdot \alpha(n))$ amortized for the union-find operations.

Prim's Algorithm

Pick a starting vertex $v_0$. Maintain a "fragment" containing $v_0$ and a priority queue of crossing edges keyed on weight. Repeatedly extract the lightest crossing edge $(u, v)$ with $u \in F$, $v \notin F$ — add $v$ to $F$ and add $(u, v)$ to the MST. Repeat until $F = V$. With a binary heap, runs in $O((n + m) \log n)$; with a Fibonacci heap, $O(m + n \log n)$. Note the structural similarity to Dijkstra's shortest-path algorithm — same control structure, different relaxation rule.

Borůvka's Algorithm

The oldest of the three (1926) and the most parallel-friendly: every fragment picks its lightest outgoing edge simultaneously, then all picked edges are added at once, fragments are merged, and the process repeats. Each round halves the fragment count, so $O(\log n)$ rounds suffice. Running time: $O(m \log n)$. Parallel variants run in $O(\log n)$ rounds with $O(m)$ work per round on a CRCW PRAM.

The LLP perspective

All three algorithms admit lattice-linear formulations on the edge-inclusion lattice $\{0, 1\}^m$ or, for Prim, on a "chosen edge per vertex" lattice:

• LLP-Kruskal. $C[j] \in \{0, 1\}$ marks selected edges. With edges sorted by weight, $j$ is forbidden when $C[j] = 0$ and the endpoints of $e_j$ are not yet connected by edges with $C[i] = 1$ for $i < j$. Advance: $C[j] := 1$. The union-find data structure makes the connectivity test amortized $O(\alpha(n))$.
• LLP-Prim. Each non-root vertex $j$ holds the weight $C[j]$ of its currently-chosen edge. A vertex is "fixed" when its parent chain reaches the root. $j$ is forbidden when it is non-fixed and the lightest edge from the fixed set into $j$ is heavier than $C[j]$. Advance: lift $C[j]$ to that cross-cut weight (which makes $j$ fixed and possibly more vertices via transitive parent chains).
• LLP-Borůvka. $G[v]$ holds the current component leader of vertex $v$. Forbidden: $G[j] \ne G[G[j]]$ — i.e. $j$'s parent chain hasn't been compressed to a star yet. Advance: $G[j] := G[G[j]]$ (one step of pointer-jumping). The classic $O(\log n)$ pointer-jumping primitive.

LLP-Borůvka is exactly the pointer-jumping kernel; the surrounding loop (alternating between picking minimum-outgoing edges and contracting fragments to stars) lives in the caller. The book develops the full algorithm in detail.

LLP-Kruskal

Edge-inclusion lattice with union-find. Auxiliary find and union methods realize iterative path-halving and root-linking; the parent scratch array is supplied by the caller.

Time complexity: $O(m \log m)$ for the edge sort, $O(m \alpha(n))$ for the union-find work, where $n$ is the number of vertices and $m$ is the number of edges.

LLP-Prim

Each non-root vertex's chosen edge is captured in $C[j]$ and $\text{parent}[j]$. Auxiliary minCrossCut, argMinCrossCut, globalMinCrossCut, and propagateFixed implement the cross-cut machinery. The forbidden predicate uses the global minimum cross-cut to ensure correctness on multi-vertex frontiers.

Time complexity: $O((n + m) \log n)$ with a binary heap, where $n$ is the number of vertices and $m$ is the number of edges.

LLP-Boruvka

The pointer-jumping kernel that contracts a rooted forest into a rooted star in $O(\log n)$ rounds. Forbidden when $G[j] \ne G[G[j]]$ (i.e. $j$ is not yet pointing to its component root); advance is one pointer-jump.

Time complexity: $O((n + m) \log n)$ across $O(\log n)$ rounds of pointer-jumping, where $n$ is the number of vertices and $m$ is the number of edges.

Constrained MST

A common side condition on MST is that a designated subset $M$ of edges must appear in the chosen spanning tree. Unlike the constrained-greedy programs in earlier chapters, the mandatory-edge requirement cannot simply be composed in conjunction with LLP-Kruskal: LLP-Kruskal's forbidden predicate for edge $e_j$ checks connectivity only through lower-indexed edges, so a naive $\&\&$ composition can accept a mandatory edge that closes a cycle with a mandatory edge committed later. Instead the two run in sequence: first commit every mandatory edge (reporting infeasible if $M$ contains a cycle), then run LLP-Kruskal on the full edge set starting from the resulting $G$ — its forbidden predicate now checks connectivity through all committed edges, mandatory and non-mandatory alike. This is equivalent to contracting $M$, computing an MST of the contracted graph, and uncontracting.

Mandatory edges

Phase 1 of the two-step procedure above: forbidden when an edge $e_j \in M$ has not yet been committed ($G[j] = \text{false}$); the advance commits it unless doing so would close a cycle with an already-committed mandatory edge, in which case the program halts ``infeasible'' (returns null). Once this terminates, LLP-Kruskal is run on the full edge set starting from the $G$ it produced.

Time complexity: $O(m \log n)$, identical to LLP-Kruskal up to constant factors; cycle tests are amortized $O(\alpha(n))$ via union-find.

boolean[] MandatoryEdges(int[] u, int[] v, boolean[] M, int[] parent) {
  boolean[] G = false;
  forbidden (j) : M[j] && !G[j] =>
    advance : {
      if (find(u[j], parent) == find(v[j], parent)) return null;
      G[j] = true;
      union(u[j], v[j], parent);
    };
  return G;
}

LLP predicates for this chapter

Each LLP program in this chapter defines a state vector $G$ and a forbidden predicate; the algorithm runs until no $j$ is forbidden. The table below lists, for each algorithm, what $G[i]$ represents and the negation of the forbidden clause from the matching .llp source.