Chapter 8. The Minimum Spanning Tree Problem

Edge-inclusion lattices, the cut property, and three classical greedy algorithms recast as LLP fixed points.

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 minimises $\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). Sequential running time: $O(m \log n)$ dominated by the sort, plus $O(m \cdot \alpha(n))$ amortised 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. Sequential 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 amortised $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 realise 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.

boolean[] LLPKruskal(int[] u, int[] v, int[] parent) {
  boolean[] C = false;
  forbidden (j) : !C[j] && find(u[j], parent) != find(v[j], parent)  =>
    advance : {
      C[j] = true;
      union(u[j], v[j], parent);
    };
  return C;
}

int find(int x, int[] parent) {
  while (parent[x] != x) {
    parent[x] = parent[parent[x]];
    x = parent[x];
  };
  return x;
}

void union(int a, int b, int[] parent) {
  int ra = find(a, parent);
  int rb = find(b, parent);
  if (ra != rb) {
    parent[ra] = rb;
  }
}

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.

double[] LLPPrim(int[] parent, boolean[] fixed,
                 double[][] W, double[] C, int root) {
  forbidden (j) : !fixed[j]
               && argMinCrossCut(j) >= 1
               && minCrossCut(j) <= globalMinCrossCut()
               && C[j] < minCrossCut(j)  =>
    advance : {
      int i = argMinCrossCut(j);
      parent[j] = i;
      C[j] = W[i][j];
      propagateFixed();
    };
  return C;
}

double minCrossCut(int j) {
  double best = infinity;
  int i = 1;
  while (i <= n) {
    if (fixed[i] && W[i][j] < best) { best = W[i][j]; };
    i = i + 1;
  };
  return best;
}

int argMinCrossCut(int j) {
  int besti = 0 - 1;
  double best = infinity;
  int i = 1;
  while (i <= n) {
    if (fixed[i] && W[i][j] < best) {
      best = W[i][j];
      besti = i;
    };
    i = i + 1;
  };
  return besti;
}

double globalMinCrossCut() {
  double best = infinity;
  int j = 1;
  while (j <= n) {
    if (!fixed[j]) {
      double m = minCrossCut(j);
      if (m < best) { best = m; };
    };
    j = j + 1;
  };
  return best;
}

void propagateFixed() {
  boolean changed = true;
  while (changed) {
    changed = false;
    int j = 1;
    while (j <= n) {
      if (!fixed[j] && fixed[parent[j]]) {
        fixed[j] = true;
        changed = true;
      };
      j = j + 1;
    };
  }
}

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.

void LLPBoruvka(int[] G) {
  forbidden (j) : G[j] != G[G[j]]  =>
    advance : G[j] = G[G[j]];
}

Constrained MST

A common side condition on MST is that a designated subset $M$ of edges must appear in the chosen spanning tree. The mandatory-edge requirement is itself a one-rule LLP program operating on the same edge-inclusion lattice $\{0, 1\}^m$ used by LLP-Kruskal, and is composed via the Lattice-Linear Language's predicate-conjunction operator $\&\&$. The problem is feasible iff $M$ is acyclic.

Mandatory edges

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). Composed with LLP-Kruskal: $[\,\textsf{LLP-Kruskal}\,\&\&\,\textsf{Mandatory}\,]$.

Time complexity: $O(m \log n)$, identical to LLP-Kruskal up to constant factors; cycle tests are amortised $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;
}

MandatoryMST

Mandatory-edge constraint for minimum spanning trees: every mandatory edge must be included. Forbidden when a mandatory edge $j$ is not yet selected; the advance includes it (or returns null if it would create a cycle).

// Mandatory-edge constraint for MST: mandatory edges must be included.
// M[j] is true iff edge j is mandatory.

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

  int find(int x, int[] parent) {
    while (parent[x] != x) {
      parent[x] = parent[parent[x]];
      x = parent[x];
    };
    return x;
  }

  void union(int a, int b, int[] parent) {
    int ra = find(a, parent);
    int rb = find(b, parent);
    if (ra != rb) {
      parent[ra] = rb;
    }
  }
}

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.