Multicommodity Flow

Picture a single network — a telecom backbone, a road map, a power grid — and several different things that all need to travel across it at once. Internet traffic from city A to city B. A separate stream from C to D. A third from E to F. Each link has a capacity: only so much can pass through it. The catch is that all these commodities share the same edges, and they fight over them.

Routing one shipment through a capacitated network is a classic, well-solved problem — it is ordinary max-flow. But the moment you have two or more distinct commodities, each with its own source and destination, sharing the same scarce links, you have a multicommodity flow problem — and the math changes character completely.

If you allow each demand to be split across many paths, the problem stays easy. But if every shipment must follow whole routes — an indivisible data stream, a train that can't be cut in half — then deciding whether everything fits at all becomes one of the hardest problems we know.

Below is a small network. Three commodities each need to get from their source to their sink, and every edge can carry only one unit of flow. Choose a route for each commodity; watch the edges they share light up red when they collide.

<p class="hint">{{hint}}</p>
<div class="wrap">
  <svg id="net" viewBox="0 0 320 220" aria-label="{{aria_network}}"></svg>
  <div class="panel">
    <div class="cmd" data-c="0"><span class="dot d0"></span><b>C1</b>: S1&rarr;T1
      <button type="button" data-next="0">{{btn_next}}</button></div>
    <div class="cmd" data-c="1"><span class="dot d1"></span><b>C2</b>: S2&rarr;T2
      <button type="button" data-next="1">{{btn_next}}</button></div>
    <div class="cmd" data-c="2"><span class="dot d2"></span><b>C3</b>: S3&rarr;T3
      <button type="button" data-next="2">{{btn_next}}</button></div>
  </div>
</div>
<div class="status" id="status">{{status_init}}</div>
<div class="btns">
  <button id="solve" type="button">{{btn_solve}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</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; }
.wrap { display: flex; gap: 1rem; flex-wrap: wrap; align-items: flex-start; }
svg { background: #f3f6f9; border: 1px solid #d6dee6; border-radius: 10px; width: 320px; max-width: 100%; height: auto; }
.panel { display: flex; flex-direction: column; gap: .5rem; min-width: 180px; }
.cmd { font-size: .92rem; display: flex; align-items: center; gap: .4rem; flex-wrap: wrap; }
.dot { width: 12px; height: 12px; border-radius: 50%; display: inline-block; }
.d0 { background: #1d70b8; } .d1 { background: #0a7d33; } .d2 { background: #b8860b; }
.cmd button { font: 600 12px system-ui, sans-serif; padding: .25rem .55rem; border: 1px solid #1d3557;
  background: #fff; color: #1d3557; border-radius: 6px; cursor: pointer; }
.edge { stroke: #b7c2cd; stroke-width: 4; stroke-linecap: round; }
.edge.used { stroke-width: 5; }
.edge.u0 { stroke: #1d70b8; } .edge.u1 { stroke: #0a7d33; } .edge.u2 { stroke: #b8860b; }
.edge.over { stroke: #e63946; stroke-width: 6; }
.node circle { fill: #fff; stroke: #5a7088; stroke-width: 1.6; }
.node text { font: 700 9px ui-monospace, monospace; fill: #1d3557; text-anchor: middle; dominant-baseline: central; }
.node.term circle { fill: #e8eef3; }
.status { font-size: 1rem; font-weight: 600; margin: .7rem 0 .5rem; min-height: 1.4em; }
.status.ok { color: #0a7d33; } .status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
.btns button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
  background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
.btns button.ghost { background: #fff; color: #1d3557; }

// Code not found

Try to fit all three at once without overloading any edge. You'll quickly feel the squeeze: two commodities want the same shortcut, but only one can have it. Press Auto-solve and the computer brute-forces every combination of routes until it finds one that fits — or proves none does. With a handful of paths per commodity that search is small, but the number of combinations multiplies with every commodity you add. That explosion is the whole story.

Multicommodity flow comes in two flavors, and they live on opposite sides of the great divide.

• Fractional flow is easy. If each commodity may be split across many paths in any proportion, the problem is just a linear program. It is solvable in polynomial time, and the famous max-flow min-cut clarity almost survives (with a known gap factor for multiple commodities).
• Integer flow is NP-hard. If every commodity must travel as a single, indivisible unit along whole routes — no half-cables, no split trains — then even deciding whether all demands can be satisfied is NP-hard. In 1976, Shimon Even, Alon Itai and Adi Shamir proved that integer multicommodity flow is NP-complete, and remarkably it stays hard with just two commodities.
• Brute force tries every combination of whole routes — one path per commodity — and the count multiplies, so it collapses beyond small instances.
• In practice engineers relax to the fractional LP, then round the answer back to whole routes, accepting some loss; or they hand the integer version to a SAT / integer-programming solver and hope the instance is friendly.

The lesson is sharp: the difficulty isn't the network or the capacities — it's the indivisibility. The instant routes must be whole, multicommodity flow joins the NP-hard family, right next to P vs NP.

"Many things, one shared network, limited capacity" describes an enormous slice of the modern world:

• Telecommunications: routing many data streams across a backbone whose links have fixed bandwidth — the canonical setting where the integer version bites.
• Traffic and transit planning: assigning vehicles or trains to roads and tracks that everyone shares, without overloading any segment.
• VLSI and chip layout: wires for different signals must reach their pins through a grid with limited channels — a multicommodity routing problem in disguise.
• Supply chains and logistics: moving distinct products through the same warehouses, trucks and ports, each leg capacity-limited.

Understand multicommodity flow and you understand why network planning is hard: it's not a lack of cleverness, it's that whole-route routing through a shared, capacitated network is genuinely intractable — a cousin of min-cost-flow where the commodities refuse to share gracefully.

Multicommodity flow hides a clean lesson about scarcity. Let flows split, and the problem dissolves into a polynomial-time linear program. Demand whole, indivisible routes, and the very same network becomes NP-hard to route — proven by Even, Itai and Shamir back in 1976, and stubbornly hard even with only two commodities.

So the next time your video call drops while the network is "busy," remember: somewhere a planner is wrestling with the same intractable puzzle. The commodities all want the best path, the edges can't carry them all, and there may be no fast algorithm that ever fully resolves the fight — that's P vs NP, wearing the uniform of a network engineer.