When several pairs share the roads

The bottleneck is the whole story is a theorem about one source and one destination. Whatever the network, the most that can travel from one to the other equals the price of the cheapest set of roads whose removal disconnects them. The flow cannot exceed the cut, because everything travelling has to cross it, and the theorem says the best flow always reaches the best cut, so each proves the other optimal.

Networks rarely serve a single pair. A road system carries traffic between many origins and destinations at once, and a communications network carries many conversations over the same links. The natural generalisation asks how much all the pairs can send together, with every road shared among them, and compares it with the cheapest set of roads whose removal separates every pair at once. The flow is still bounded by that cut, for the same reason as before. What fails is the other half: with three pairs, the best flow can fall strictly short of the best cut.

Three pairs through one hub #

The smallest network that shows it has four places and three roads.

Every route between two of the outer places runs through the hub and uses two of the three roads. If each of the three pairs sends half a unit, each road carries two of those halves and is exactly full, and the pairs have sent 3/2 between them.

Separating every pair is dearer. Removing one road isolates one outer place, but leaves the other two joined through the hub. Removing two roads isolates two places and leaves the third alone at the hub, and now no pair is connected. So the cheapest separating cut costs 2 and the largest flow is 3/2: neither number can be improved, and they are different.

The same hub gives a third number. If the pairs must send whole units, one pair takes two roads and the remaining road is useless on its own, so only 1 unit gets through. The whole-unit flow, the fractional flow and the cut stand at 1, 3/2 and 2, which for a single pair would all be the same number.

Prices that prove 3/2 is the most #

That 3/2 is the best the pairs can do needs a proof, since the claim is about every possible routing. The proof is a set of prices, one per road.

Put a price of 1/2 on each of the three roads. Every route between two outer places crosses two roads and so costs 1 at these prices. Now take any flow at all and add up, over every road, its price times what the road carries. Counted road by road, that total is at most each price times the road’s capacity, which is 3/2. Counted route by route, it is each unit of flow times the cost of its route, at least 1 per unit. So no flow can exceed 3/2, and the half-unit flow reaches it.

This is the pattern of two numbers that have to meet: the largest flow is a linear program, its dual asks for the cheapest prices under which every route costs at least 1, and the two optima are equal. The prices are what a constraint is worth — adding a little capacity to any one road would let the flow grow by half that amount.

The prices are a cut that has been allowed to be fractional. A real cut is the special case in which every price is 0 or 1: a road priced at 1 is removed, and every route costing at least 1 means every route crosses a removed road. The linear program’s best prices here are 1/2, 1/2 and 1/2, and no choice of whole prices costs less than 2. The flow matches the fractional cut exactly, as duality says it must; what the pairs cannot match is the cut’s insistence on whole roads.

Why a single pair never shows this #

For one pair the prices can always be chosen whole. The cheapest cut’s roads priced at 1 and every other road at 0 already give a set of prices whose total equals the largest flow, and the corners of the single-pair problem are whole numbers, as the corners of the assignment problem are. That is why one theorem covers both the flow and the cut when there is only one pair.

The hub breaks this in a way that has a familiar shape. Cutting a spoke of the hub removes one outer place, and separating every pair means removing at least one place from each pair. The pairs a–b, b–c and a–c form a triangle, so the cheapest cut is the smallest set of corners touching every side of a triangle, which is two. The flow sends amounts along the triangle’s sides with no corner overloaded, which is a matching allowed to be fractional, and a triangle’s best fractional matching puts 1/2 on each side.

Those halves are the ones where the corners stop being whole finds for matching: an odd cycle is exactly what makes a fractional corner that no whole assignment reaches. The gap on the hub is the triangle’s oddness, passed through a network.

The gap grows on larger hubs #

The triangle is the smallest odd cycle, and a hub with more spokes produces a larger structure of the same kind.

With $k$ spokes every pair of outer places wants to send, so the pairs form a complete network on $k$ places. Every unit of flow uses two spokes, and the spokes hold $k$ units between them, so no flow can exceed $k/2$. That ceiling is reached by sending $1/(k - 1)$ between every pair: each spoke is used by $k - 1$ pairs and so carries exactly one unit. Half a unit on every pair, which worked on three spokes, would overload every spoke once there are four. The cut must leave at most one outer place attached to the hub, so it removes $k - 1$ spokes.

The ratio of the two is

$$\frac{k - 1}{k/2} = \frac{2(k - 1)}{k},$$

which is 1.333 at three spokes and 1.714 at seven, and approaches 2 without reaching it. The whole-unit column is the largest matching on $k$ places, $\lfloor k/2 \rfloor$ units, so it lags the fractional flow by half a unit whenever $k$ is odd.

Two is not an accident of hubs. On any network shaped like a tree, Garg, Vazirani and Yannakakis proved that the cheapest separating cut is never more than twice the largest flow. On general networks the gap can be larger, growing with the logarithm of the number of pairs, and they showed that logarithm is the right order: no network does worse by more than a constant factor, and on expanders — networks built so that every set of places has many roads leaving it — the gap really does grow that fast.

Turning prices into a cut #

The gap is also a method, because the prices can be rounded into a cut. Read each price as a length on its road, so that every route between a pair is at least 1 long. Grow a region around one source, taking in places in order of their distance from it, and stop at a radius below 1/2 where the roads leaving the region are cheap compared with the priced capacity already inside. Remove those roads, set the region aside, and start again from any source still joined to its partner.

A region of radius below 1/2 can never hold both ends of any pair, since the two ends are at least 1 apart and each would be within 1/2 of the centre. So the removed roads separate every pair. Garg, Vazirani and Yannakakis showed that a good stopping radius always exists and that the removed roads cost at most a logarithmic factor more than the total of the prices — which is the flow. The flow, which is quick to compute, therefore bounds the cheapest cut from below and leads to a cut not far above it.

On the hub the method has nothing to decide. Every spoke is 1/2 long, so a region around a of radius below 1/2 holds a alone and costs its spoke; the same happens at b; and c is then separated from everyone. The rounding removes two spokes for a price of 2, which is the cheapest cut itself, and the whole loss of 2 against 3/2 is the gap that no rounding can avoid.

Two pairs still meet their cut #

Between one pair, where flow and cut always meet, and three, where they can come apart, there is a case that holds on. T. C. Hu proved in 1963 that for two pairs sharing an undirected network, the largest total flow equals the cheapest cut separating both, with a condition attached that the example below makes visible.

Either pair alone could send 2, and together they cannot send 4, because their routes have to cross. The best they can do is 3, and the two marked roads — the top road from $s_1$ to $u$, capacity 2, and the bottom road from $t_2$ to $v$, capacity 1 — cost 3 and cut $s_1$ and $t_2$ off from the other four places, which separates both pairs. Flow and cut meet at 3, as Hu’s theorem says.

The routes drawn send one whole unit and four halves. No routing in whole units reaches 3, and the reason is a parity count. This network has three different cuts of price 3 — the top and bottom roads between the first two columns, the top and bottom roads between the last two, and the three roads running down — and together they contain all seven roads. A flow of 3 would fill every road of every one of those cuts, so it would fill every road. But the roads at $u$ have capacities 2, 2 and 1, which total 5, and $u$ is neither a source nor a destination: every unit passing through $u$ arrives on one road and leaves on another, using two of those five. Whole units can use only an even number of them, so one is always left over.

Half units repair the count, and Hu’s theorem guarantees they always suffice: the largest flow for two pairs can be reached with every route carrying a whole or half unit. Rothschild and Whinston showed in 1966 that whole units suffice whenever the capacities at every place add to an even number. Here they add to 3 at $s_1$, $s_2$ and $v$ and to 5 at $u$, and only $t_1$ and $t_2$ are even.

For two pairs the best prices can be a cut #

The prices tell the same story from the other side. On the grid, put a price of 1 on the top road from $u$ to $s_2$ and on the bottom road from $v$ to $t_1$, and 0 on the other five. Those two roads separate the last column from the rest, so every route from $s_1$ to $t_1$ and every route from $s_2$ to $t_2$ crosses one of them and costs at least 1. The prices times the capacities total 2 + 1 = 3, which equals the flow, so these whole prices are among the best there are.

That is not luck in the choice of grid. Hu’s theorem says the flow for two pairs always equals a real cut, and a real cut with its roads priced at 1 is always a valid set of prices, so for two pairs a best set of prices can always be chosen whole. The certificate for the flow is a cut, exactly as for one pair.

On the hub no whole prices are best, and the half-prices are not merely one option among several. If the three spokes are priced $y_a$, $y_b$ and $y_c$, each route requires two of them to sum to at least 1; adding the three requirements gives $2(y_a + y_b + y_c) \ge 3$, and a total of exactly 3/2 forces every requirement to hold with equality, which forces every price to be 1/2. The only certificate for 3/2 is the fractional one.

How rare the gap is in small networks #

The theorem for two pairs is visible in the counts: 120 random networks, and in every one the flow met the cut. The three-pair counts are the instructive part. Eighty random networks with three pairs produced no gap at all, although the hub proves that a gap of 3/2 against 2 exists with only four places and three roads.

This is a case where small examples mislead. A gap needs the pairs to be tangled in an odd way — routes that must share roads in a pattern like the triangle on the hub — and small random networks with unit roads rarely arrange that. Anyone testing the claim that flow meets cut for three pairs on a few hundred random examples would find it true every time, and would be wrong. The hub is a counterexample that has to be built rather than stumbled upon.

The same counts show a quieter version of the same lesson about whole units. In none of the 120 two-pair networks did whole units fall short, although the grid above shows that they can. A shortfall needs every cheapest cut to be full and an odd total at a place those cuts pass through, and random networks of unit roads did not happen to arrange both; the grid was found by searching for it.

A logarithmic gap that six places cannot draw #

Every flow in the tables was found by trying every route. The networks are small enough that every simple route between every pair can be listed, and the largest flow is then an exact linear program solved in fractions; the prices that prove it optimal are checked against every route. For large networks the number of routes explodes, and the linear program has to be solved without listing them.

The logarithmic gap is described, not drawn. The networks that achieve it are large and spread traffic evenly across many roads, and no six-place drawing can show a ratio growing with the number of pairs. The hubs show only the approach to 2.

And the cut is found by trying every set of roads. Finding the cheapest cut separating several pairs is hard in general — already hard on a hub when the pairs are chosen freely, where it becomes the problem of choosing the fewest outer places that touch every pair. That hardness is the other side of the gap: if flow always met cut, the flow computation, which is quick, would hand over the cut’s price.

Pairs one at a time, and pairs all at once #

There are two ways to ask several pairs about a network, and they have opposite fortunes. Asking each pair separately how much it could send if it had the network to itself gives a collection of single-pair answers, and those are as well behaved as the single-pair theorem: fifteen of them for six places sit on a tree with five numbers, which is the subject of one tree for every cut.

Asking all pairs at once, with every road shared, is the question here, and it has no such structure. The flow is a linear program and is computed exactly; the cut is a whole-number problem and is hard; and the ratio between them is what a network’s shape allows. The certificate that made the single-pair theorem so useful — a cut that proves a flow cannot be beaten — survives only in its fractional form.

The same move from one to many recurs across the subject. Hall’s theorem says a set of people can all be matched to tasks unless some group of them has too few tasks between them — one bottleneck and nothing else — and it is max-flow min-cut for a single source of people and a single destination of tasks. Prices for every person and task certify the best assignment in the same way the prices on the hub certify 3/2.

Still open: whether flat networks keep the gap bounded #

The gap has a second version that measures a flow differently: every pair has a demand, and the flow is the largest fraction of all the demands that can be delivered simultaneously. Its partner cut is the sparsest one — the set of roads with the smallest capacity relative to the demand it separates. On general networks this gap too can grow with the size of the network.

For networks that can be drawn flat, with no two roads crossing, Gupta, Newman, Rabinovich and Sinclair conjectured in 2004 that the gap stays below a fixed constant however large the network is. It is proved for networks built up by joining smaller pieces in series and in parallel, where the worst ratio is known exactly to be 2, the same number the hubs approach. For flat networks in general the best bound proved, due to Rao in 1999, still grows like the square root of the logarithm of the number of places. Whether every flat network keeps its flow within a constant factor of its sparsest cut is open.

A cut that proves, and a cut that only bounds #

For one pair, a cheapest cut is a certificate: it shows the flow can go no higher, and it is always exactly as large as the flow. For three pairs sharing one hub, the cheapest cut is 2 while the flow stops at 3/2, and the proof that 3/2 is best is a set of half-prices that no real cut can imitate.

When a max-min equality stops holding, look for the relaxation that still holds it. Here the flow meets a cut that is allowed to remove half a road, and the distance from that fractional cut to a real one is the whole of the gap — an odd triangle on the hub, a logarithm on the worst networks, and on two pairs nothing at all.