Introduction

You need to connect a handful of towns with cable, using as little as possible. The natural move is to link them directly in the cheapest tree that touches them all — a minimum spanning tree, which you can find quickly and exactly.

But there's a twist that feels almost like cheating: you're allowed to add brand-new junction points that aren't towns at all — places where cables meet and split. Drop a junction in just the right spot and the total length shrinks. For three towns at the corners of a triangle, a single junction in the middle beats every spanning tree.

Those extra meeting points are Steiner points, and the shortest network using them is a Steiner tree. The catch: while the spanning tree is easy, finding the optimal Steiner tree — where to add junctions and how to wire them — is NP-hard.

The Shortest Network

Try it. Four towns sit at the corners of a square. Toggle between the spanning tree (connect towns directly) and the Steiner tree (add two junction points where cables meet at 120°). The total length and the saving update as you switch.

<p class="hint">Four towns at the corners of a square (10 km a side). Switch between the plain <b>spanning tree</b> and the <b>Steiner tree</b> with two extra junctions, and watch the total cable — and the saving — change.</p>
<div class="toggle">
  <button id="bmst" type="button" class="active">Spanning tree</button>
  <button id="bst" type="button">Steiner tree</button>
</div>
<svg id="svg" viewBox="0 0 300 270" class="svg"></svg>
<div class="meter">
  <div>Total cable: <b id="len">—</b></div>
  <div id="save" class="save"></div>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.toggle { display: flex; gap: 0; margin-bottom: .7rem; border: 1px solid #457b9d; border-radius: 8px; overflow: hidden; width: fit-content; }
.toggle button { font: 600 14px system-ui; padding: .5rem 1.1rem; border: none; background: #fff; color: #457b9d; cursor: pointer; }
.toggle button.active { background: #457b9d; color: #fff; }
.svg { width: 100%; max-width: 420px; background: #f4f7f9; border: 1px solid #e2e6eb; border-radius: 10px; display: block; }
.cable { stroke: #2a9d8f; stroke-width: 3.5; stroke-linecap: round; }
.town { fill: #1d3557; }
.tlbl { font: 700 12px system-ui; fill: #1d3557; text-anchor: middle; }
.steiner { fill: #e76f51; }
.slbl { font: 600 10px system-ui; fill: #e76f51; text-anchor: middle; }
.meter { display: flex; gap: 1.5rem; align-items: center; margin-top: .8rem; font-size: 1.05rem; flex-wrap: wrap; }
.meter b { color: #1d3557; }
.save { font-weight: 800; color: #0a7d33; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Steiner tree vs minimum spanning tree on a unit square.
// Spanning tree = 3 sides = 30 km. Steiner tree adds two junction points where cables meet at 120 degrees, for the provably shortest network (~27.3 km).
const SCALE = 18; // px per km, square side = 10 km
// towns (corners), px coords
const T = { A: [60, 40], B: [240, 40], C: [60, 220], D: [240, 220] };
// Steiner junctions on the horizontal midline
const t = 0.5 * (1 - 1 / Math.sqrt(3)) * 180;
const S1 = [150 - t, 130], S2 = [150 + t, 130];
function dist(p, q) { return Math.hypot(p[0] - q[0], p[1] - q[1]); }

const MST_EDGES = [['A', 'B'], ['A', 'C'], ['B', 'D']]; // 3 sides
function mstLen() { return MST_EDGES.reduce((s, [a, b]) => s + dist(T[a], T[b]), 0) / SCALE; }
const ST_SEGMENTS = () => [[T.A, S1], [T.C, S1], [T.B, S2], [T.D, S2], [S1, S2]];
function stLen() { return ST_SEGMENTS().reduce((s, [p, q]) => s + dist(p, q), 0) / SCALE; }

let mode = 'mst';

function render() {
  let s = '';
  if (mode === 'mst') {
    MST_EDGES.forEach(([a, b]) => { s += line(T[a], T[b]); });
  } else {
    ST_SEGMENTS().forEach(([p, q]) => { s += line(p, q); });
    [S1, S2].forEach((p, i) => { s += '<circle class="steiner" cx="' + p[0] + '" cy="' + p[1] + '" r="6"/>'; });
    s += fmt('<text class="slbl" x="%v%" y="%v2%%v3%">junction</text>', { v: S1[0], v2: S1[1], v3: 20 });
    s += fmt('<text class="slbl" x="%v%" y="%v2%%v3%">junction</text>', { v: S2[0], v2: S2[1], v3: 20 });
  }
  for (const k in T) { const p = T[k]; s += '<circle class="town" cx="' + p[0] + '" cy="' + p[1] + '" r="8"/>'; s += '<text class="tlbl" x="' + p[0] + '" y="' + (p[1] + (p[1] < 130 ? -14 : 24)) + '">' + k + '</text>'; }
  document.getElementById('svg').innerHTML = s;
  const mst = mstLen(), st = stLen();
  const cur = mode === 'mst' ? mst : st;
  document.getElementById('len').textContent = fmt('%cur% km', { cur: cur.toFixed(1) });
  const save = document.getElementById('save');
  if (mode === 'st') { save.textContent = fmt('Saves %v% km (%round%%) vs the spanning tree.', { v: (mst - st).toFixed(1), round: Math.round((1 - st / mst) * 100) }); }
  else { save.textContent = 'Switch to the Steiner tree to see the saving.'; save.style.color = '#777'; }
  if (mode === 'st') save.style.color = '#0a7d33';
}
function line(p, q) { return '<line class="cable" x1="' + p[0] + '" y1="' + p[1] + '" x2="' + q[0] + '" y2="' + q[1] + '"/>'; }

document.getElementById('bmst').addEventListener('click', () => { mode = 'mst'; document.getElementById('bmst').classList.add('active'); document.getElementById('bst').classList.remove('active'); render(); });
document.getElementById('bst').addEventListener('click', () => { mode = 'st'; document.getElementById('bst').classList.add('active'); document.getElementById('bmst').classList.remove('active'); render(); });
render();
Result
Console

The spanning tree uses three full sides; the Steiner tree, with its two clever junctions, is noticeably shorter. That little saving — around 9% here, and provably the best possible for a square — is exactly the prize that makes the problem worth its NP-hard difficulty.

The Hard Part

The gap between easy and hard here is razor-thin and fascinating:

  • The minimum spanning tree is easy. Connecting given points (no new junctions) is solved in near-linear time by classic greedy algorithms (Kruskal, Prim).
  • Adding junctions makes it NP-hard. The moment you may insert Steiner points, the problem explodes: there are infinitely many places to put them and exponentially many ways to wire them.
  • Checking is easy. Given a proposed network, just add up the edge lengths.
  • The spanning tree is a good start. An MST is never more than about 2× the optimal Steiner length, so it's a built-in approximation — and the best known algorithms push the ratio down to roughly 1.39 using linear-programming relaxations.
  • Special cases help. On a grid (rectilinear Steiner tree, used in chip design) and in the plane, specialized methods and heuristics do very well.

It's a beautiful illustration of how a tiny extra freedom — "you may add points" — can flip an easy problem into a hard one.

Where It Matters

Saving length on a network saves real money and material:

  • Telecom and fiber: laying cable to connect sites with minimum trenching.
  • Chip and PCB design: routing wires between components — rectilinear Steiner trees are everywhere in VLSI.
  • Transport and pipelines: connecting hubs with minimal road, rail or pipe.
  • Phylogenetics: building evolutionary trees where internal nodes (Steiner points) are inferred ancestors.
  • Utility networks: power, water and gas distribution layouts.

Because even a few percent saved scales across millions of connections, Steiner-tree heuristics are a staple of network and chip design tools.

Conclusion

The Steiner tree is a story about the cost of freedom. Take away the right to add junctions and the problem is a textbook-easy spanning tree. Hand that one small freedom back, and the search space explodes into NP-hardness — for a saving that's often just a few percent.

But those few percent matter at scale, and the math is gracious: the easy spanning tree is itself a guaranteed approximation, and clever relaxations get closer still. It's the recurring kindness of hard problems — even when the optimum is out of reach, a simple idea usually gets you most of the way there.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/steiner-tree/Content licensed under CC BY-NC 4.0.