Cairn
algorithms · minimum spanning tree · O(E log E) naive (O(E) optimal)

↩ back to Minimum Spanning Trees

Minimum Bottleneck Spanning Tree

Kruskal's, Prim's, and Borůvka's algorithms all minimize the same thing: the total weight of the spanning tree, every edge's cost added up. A minimum bottleneck spanning tree (MBST) minimizes something different — the weight of the single most expensive edge the tree is forced to use, ignoring everything else in the sum. The distinction matters whenever the sum isn't really the cost that matters: a courier network's end-to-end speed is capped by its single slowest required hop, not by adding every hop's time together; a set of pipes can only carry as much pressure as its narrowest required section can survive, no matter how wide all the others are. For those questions, a tree that's merely cheap on average is the wrong answer — what's wanted is the tree whose worst edge is as good as any spanning tree's worst edge can possibly be.

The two problems turn out to be closely related, just not identical. Every minimum spanning tree is automatically a minimum bottleneck spanning tree too — but, as the demo below shows on this site's own trail network, not every minimum bottleneck spanning tree is a minimum spanning tree. Minimizing the bottleneck is a strictly weaker requirement than minimizing the total, so it admits more solutions; the total-weight-minimal one is always among them, but so are others.

Try it

The same seven-waypoint trail network Kruskal's, Prim's, and Second-Best Spanning Tree all use — same nodes, same ten costs. Four of its trails are bridges: cut any one of them and the network splits in two, so every spanning tree needs all four, no choice involved. The other three trails — Basecamp–Spring, Spring–Saddle, Basecamp–Saddle — form the network's only triangle, so any spanning tree uses exactly two of those three and leaves one out. Click one of the three below to see the spanning tree that results from leaving it out; the remaining leftover trails (weight 8, 9, 10) never belong to any minimum bottleneck tree here at all — including any of them would need a costlier edge than the network's forced bottleneck already is.

Why it works

Kruskal's own correctness argument rests on the cut property: the cheapest edge crossing any split of the nodes belongs to some MST. Minimum bottleneck trees rest on its usual counterpart, the cycle property: for any cycle in the graph, the single most expensive edge on that cycle is never needed to keep the graph connected as cheaply as possible, because every other edge on the cycle already offers some alternate route between its endpoints. Drop the priciest edge on every cycle and what's left is still connected, using nothing more expensive than necessary — which is exactly what Kruskal's own cycle-rejection rule already does on the way to building an MST, without ever being told to think about bottlenecks specifically. That's why Kruskal's output is always both a minimum spanning tree and a minimum bottleneck spanning tree at once.

But Kruskal's rule is stricter than bottleneck-minimality actually asks for. On this page's one triangle (Basecamp–Spring 2, Spring–Saddle 4, Basecamp–Saddle 6), Kruskal specifically drops the priciest edge, 6, because that's the one still uninspected — and therefore the one that closes the loop — once the sorted scan reaches it. Bottleneck-minimality doesn't care which of the three gets dropped: all three remaining trees keep the exact same maximum edge, 7 (Overlook–Summit, a bridge elsewhere in the network that every spanning tree is forced to include), so all three qualify as minimum bottleneck spanning trees. Only one of them — the one that drops 6, Kruskal's own answer — is also minimal on total weight (22, against 24 and 26 for the other two). Every MST is an MBST; the demo's other two candidates are the counterexample to the reverse.

Reference implementation

Finding the bottleneck value itself needs nothing beyond Kruskal's own scan — the weight of the last edge accepted before the tree finishes spanning is the bottleneck, whether or not minimizing it was the actual goal. Checking whether some other candidate tree is also a valid MBST is a separate, cheap question: is it a spanning tree at all, and does every one of its edges stay at or under that same bottleneck value?

function bottleneckValue(numNodes, edges) {
  // Kruskal's own scan — the last accepted edge's weight is the bottleneck.
  const sorted = edges.slice().sort((x, y) => x.w - y.w);
  const parent = Array.from({ length: numNodes }, (_, i) => i);

  function find(x) {
    let root = x;
    while (parent[root] !== root) root = parent[root];
    while (parent[x] !== root) { const next = parent[x]; parent[x] = root; x = next; }
    return root;
  }

  let edgesUsed = 0, bottleneck = 0;
  for (const edge of sorted) {
    const rootA = find(edge.a), rootB = find(edge.b);
    if (rootA === rootB) continue; // cycle — reject, same as Kruskal
    parent[rootA] = rootB;
    edgesUsed++;
    bottleneck = edge.w;
    if (edgesUsed === numNodes - 1) break;
  }
  return bottleneck;
}

function isValidMBST(numNodes, treeEdges, bottleneck) {
  // A candidate is a valid MBST iff it's a spanning tree at all, and every
  // edge in it stays at or under the known-minimal bottleneck value.
  if (treeEdges.length !== numNodes - 1) return false;
  if (treeEdges.some(e => e.w > bottleneck)) return false;

  const parent = Array.from({ length: numNodes }, (_, i) => i);
  function find(x) { let r = x; while (parent[r] !== r) r = parent[r]; return r; }
  for (const e of treeEdges) {
    const rootA = find(e.a), rootB = find(e.b);
    if (rootA === rootB) return false; // cycle — not a tree
    parent[rootA] = rootB;
  }
  return true; // numNodes - 1 acyclic edges among numNodes nodes = connected
}

Pitfalls

A valid MBST isn't automatically the MST — checking the bottleneck alone can't tell them apart. All three trees in the demo above pass isValidMBST with the identical bottleneck value, 7. Code that stops at "bottleneck matches, ship it" has a 2-in-3 chance of returning a tree that's needlessly expensive overall on this page's own network (24 or 26 instead of 22) — verified directly against the reference implementation above, not just reasoned about. If total weight matters at all, minimizing the bottleneck first and then breaking ties on weight (which is exactly what Kruskal's own scan already does for free) is the safe default, not an afterthought.

The bottleneck edge itself is not always safe to drop, even though it's the most expensive edge in the tree. It's tempting to assume the priciest edge in any tree is a candidate for being swapped out — but that's only true of edges sitting on a cycle. Overlook–Summit (7) sets this network's bottleneck and is also its single most expensive edge in every valid tree, yet it's a bridge, not part of any cycle: remove it from the graph entirely and Meadow and Summit split off into their own component, fully disconnected from the other five waypoints (checked directly against the network's adjacency, not assumed from the diagram). The cycle property only license dropping the max edge on a cycle — the max edge in the final tree overall is under no such guarantee, and here it happens to be the one edge nothing can route around.

Disconnected input has no spanning tree of either kind. Same failure mode as Kruskal's own pitfall — the scan just runs out of edges early, having built minimum bottleneck trees for each connected piece separately with no way to notice or complain on its own.

Measuring the real crossover

The Complexity section below credits Camerini's 1978 algorithm with an expected O(E) bound and says it "earns its keep" once E is large enough to make skipping Kruskal's sort worthwhile — but names no actual number, and admits the page's own ten-edge network is "much too small to demonstrate" it. Measured directly: a JavaScript implementation of the median-threshold-and-recurse idea described in Complexity, built from scratch rather than copied from a library, correctness-checked against this page's own bottleneckValue above across 10,000 random connected graphs (sizes up to 300 nodes, plus two deliberately adversarial weight distributions — a narrow 1–3 range to force heavy ties, and every edge sharing one single weight — both of which broke an early draft by sending it into infinite recursion, caught before trusting any timing number) — 0 mismatches.

function partitionByRank(arr, k) {
  // Hoare quickselect: rearranges arr in place so every element before
  // index k is no heavier than every element from k on.
  let lo = 0, hi = arr.length - 1;
  while (lo < hi) {
    const pivotIndex = lo + ((Math.random() * (hi - lo + 1)) | 0);
    const pivotVal = arr[pivotIndex].w;
    [arr[pivotIndex], arr[hi]] = [arr[hi], arr[pivotIndex]];
    let store = lo;
    for (let i = lo; i < hi; i++) {
      if (arr[i].w < pivotVal) { [arr[i], arr[store]] = [arr[store], arr[i]]; store++; }
    }
    [arr[store], arr[hi]] = [arr[hi], arr[store]];
    if (k === store) return;
    else if (k < store) hi = store - 1;
    else lo = store + 1;
  }
}

function bottleneckValueCamerini(numNodes, edges) {
  if (numNodes <= 1 || edges.length === 0) return -Infinity;
  if (edges.length === 1) return edges[0].w; // rank-split degenerates below 2 edges

  const arr = edges.slice();
  const k = arr.length >> 1; // median rank — guarantees both halves shrink
  partitionByRank(arr, k);
  const low = arr.slice(0, k), high = arr.slice(k);

  const parent = Array.from({ length: numNodes }, (_, i) => i);
  function find(x) {
    let root = x;
    while (parent[root] !== root) root = parent[root];
    while (parent[x] !== root) { const next = parent[x]; parent[x] = root; x = next; }
    return root;
  }
  let components = numNodes;
  for (const e of low) {
    const ra = find(e.a), rb = find(e.b);
    if (ra !== rb) { parent[ra] = rb; components--; }
  }

  if (components === 1) {
    // Cheap half alone already connects everything — the true bottleneck is
    // in there somewhere, and every edge in `high` is irrelevant.
    return bottleneckValueCamerini(numNodes, low);
  }

  // Contract each surviving component to one super-vertex, then recurse on
  // just the edges crossing between components.
  const relabel = new Array(numNodes).fill(-1);
  let next = 0;
  for (let i = 0; i < numNodes; i++) {
    const root = find(i);
    if (relabel[root] === -1) relabel[root] = next++;
  }
  const bridgeEdges = [];
  for (const e of high) {
    const ra = relabel[find(e.a)], rb = relabel[find(e.b)];
    if (ra !== rb) bridgeEdges.push({ a: ra, b: rb, w: e.w });
  }
  return bottleneckValueCamerini(next, bridgeEdges);
}

partitionByRank is the same in-place rank split Quickselect uses, just applied to edge weights instead of array values — picking exactly the median rank (not a value-based threshold) is what guarantees low/high always split roughly in half even when many edges tie on weight; an earlier draft split on a value comparison instead and looped forever on the all-edges-equal-weight adversarial case mentioned above, since nothing distinguished "low" from the full edge set.

E (edges)    naive sort    Camerini    naive÷Camerini
10           0.0019 ms     0.0029 ms   0.67
20           0.0027 ms     0.0025 ms   1.07
50           0.0059 ms     0.0044 ms   1.35
100          0.0136 ms     0.0092 ms   1.47
200          0.0324 ms     0.0165 ms   1.97
500          0.1042 ms     0.0269 ms   3.88
1,000        0.244 ms      0.052 ms    4.73
5,000        1.53 ms       0.28 ms     5.38
20,000       7.87 ms       1.51 ms     5.20
100,000      49.4 ms       9.18 ms     5.38
1,000,000    1,039 ms      212 ms      4.91

Both algorithms timed on identical random connected graphs (sparse, edges ≈ 4× the node count), each number averaged over thousands of repetitions to wash out GC and JIT warmup noise. The real crossover lands between 10 and 20 edges — not "large," in any everyday sense of the word, just larger than the one graph on this page. The advantage climbs through the hundreds and thousands of edges before settling around 5× (4.9×–5.4×) from a few thousand edges all the way out to a million, essentially flat across three more orders of magnitude.

That plateau is the more interesting number, because it's not what the raw operation count predicts. Instrumenting both algorithms' real comparison/union-find work directly: at E=100 the sort-based scan performs 534 comparator calls against Camerini's 162 edge-touches (3.3×); at E=1,000,000 it's 18,605,119 against 1,020,615 (18.2×) — the gap between O(E log E) and O(E) widening exactly as the Big-O difference predicts, unboundedly. Wall-clock time doesn't track that at all once past the small sizes — it plateaus around 5× instead of climbing toward 18×, because every one of Camerini's recursive calls pays for an array slice, a fresh parent array, and a relabeling pass that a single comparator call inside Array.prototype.sort never has to. Same shape as Karatsuba Multiplication's own crossover measurement: a real, lasting win, just smaller in wall-clock than the operation-count gap on its own would suggest.

Complexity

Time: O(E log E) the way this page computes it — Kruskal's own sort, since that's the simplest way to get both the tree and its bottleneck value at once, and the reference implementation above does no better. But bottleneck-minimality is a strictly weaker ask than total-weight-minimality, and it turns out to be solvable in genuinely less time: repeatedly picking the median remaining edge weight as a threshold, checking with one Union-Find pass whether the edges at or under that threshold already connect the graph, and recursing into only the half of the weight range that still needs narrowing (never re-sorting, never revisiting the half already ruled out) finds the bottleneck value in expected O(E) — the same threshold-and-recurse shape as quickselect, applied to edge weights instead of array elements. Camerini's 1978 algorithm is the standard reference for this result; see measuring the real crossover above for where it actually starts winning (around 10–20 edges) and how much it wins by at scale (a wall-clock plateau around 5× (4.9×–5.4×), well short of the ever-widening operation-count gap). Space: O(V + E) — the edge list plus Union-Find's parent array, same as Kruskal alone.

For a decision guide across all twelve of this site's Minimum Spanning Trees entries — including where this page fits once the real cost is a worst-hop cap rather than a sum — see Choosing a Minimum Spanning Tree Algorithm.