The Shortest Network

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.

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">{{hint}}</p>
<div class="toggle">
  <button id="bmst" type="button" class="active">{{btn_mst}}</button>
  <button id="bst" type="button">{{btn_st}}</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; }

// Code not found

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 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.

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.

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.