Three places cut apart

The bottleneck is the whole story proves that the most a network can carry from one place to another equals the cheapest set of roads whose removal separates them. One tree for every cut goes further and holds the cheapest cut between every pair of places in a single tree of five numbers. Both are about separating two places. The moment a third place has to be separated from both of the others — and they from each other — at the same time, the tree stops helping, the flow theorem stops applying, and the problem changes character.

It is called the multiway cut: given a network with a capacity on every road and some number $k$ of marked places, find the cheapest set of roads whose removal leaves no route between any two of the marked places. For $k = 2$ it is the ordinary cheapest cut, solved exactly by a maximum flow. For $k = 3$ it was shown in 1994 to be as hard as the hardest problems of its kind, which in practice means that no method much better than trying possibilities is known. What is known is how close a cheap method can get, and why.

The cheapest way to cut three places apart #

The network drawn has eight places, three of them lettered, and fourteen roads with capacities from one to five.

A three-way cut is the same thing as a colouring: give each place one of three colours, with A, B and C given their own, and cut every road whose two ends differ. Any set of roads separating the lettered places arises this way — colour each place by which lettered place it can still reach, or arbitrarily if none — so trying every colouring finds the cheapest. There are five unlettered places, so $3^5 = 243$ colourings, and the cheapest costs 13. It gives A two of the unlettered places and B three, leaves C on its own at the bottom, cut off by its two roads of 5 and 4, and splits the middle with four roads of capacity 1.

Nothing about that answer is visible to a two-place method. The cheapest cut between A and B alone is not part of it, and neither is the cheapest between B and C: the three-way answer shares roads between the three separations, and a road cut once counts once however many pairs it helps separate.

Why two places are easy and three are not #

It is worth seeing what the two-place case has that the three-place case lacks, because the difference is a single property and the rest of the essay follows from it.

A cut between two places comes with a certificate. If a flow of 9 units can be routed from A to B within the capacities, then no cut between them costs less than 9, because every unit has to cross every cut; and the flow theorem says such a flow always exists matching the cheapest cut. So the cheapest cut can be proved cheapest by exhibiting a flow, and the flow can be found by pushing units along routes until no route has room. Both halves are local: a flow is built one route at a time, and a cut is read off where the pushing stops.

A three-way cut has no such partner. One could route flow between every pair of lettered places at once, but a road cut in the three-way answer may carry flow for two different pairs, and when several pairs share the roads the most they can send together is no longer equal to the cheapest set of roads separating them all. Flow-type certificates stop matching the cut exactly as soon as there are three places, and without a matching certificate there is no local way to confirm that a cut is cheapest — which is the ordinary sign that a problem is hard.

In the colouring picture the same fact looks like this. A two-sided cut is a colouring with two colours, and the cost of a two-colouring has a property called submodularity: moving a set of places from one side to the other changes the cost by an amount that shrinks as the side it joins grows. That is what makes two-colourings searchable by local improvement. With three colours the property fails — a place moving from A’s colour to B’s can make C’s separation dearer or cheaper — and local improvement can stall at a colouring that no single move improves and that is not the cheapest.

Each place cut off on its own #

What a two-place method can compute is the cheapest way to cut off one lettered place from the other two. Merge the other two into a single place, and it is an ordinary cheapest cut, found exactly by a maximum flow.

These are the isolating cuts. A’s costs 9 and cuts A off with its two roads directly. B’s costs 8 and takes B together with two middle places. C’s costs 9 and is the pair of roads into C. Each is exactly right for its own question — the cheapest way to separate that one place from the rest — and each is found by the theorem that makes two-place cutting easy.

Any three-way cut contains an isolating cut for each lettered place, since it certainly separates each from the other two. So the three isolating cuts are lower bounds of a kind. But they are three different sets of roads, and the three-way cut has to be one set that does all three jobs at once.

The shortcut: keep the two cheapest #

In 1994 Elias Dahlhaus, David Johnson, Christos Papadimitriou, Paul Seymour and Mihalis Yannakakis, in the paper that proved the three-way problem hard, also proved the obvious shortcut good. Take the isolating cut of every lettered place, throw away the dearest, and remove the roads of the rest. If A and B are each cut off from everything else, C is cut off too, since anything C could reach would lead to A or B — so for three places, two isolating cuts suffice.

On this network the shortcut pays 17 where 13 would do. The two cheapest isolating cuts, B’s and A’s, share nothing: A’s cuts A’s own two roads, B’s cuts four middle roads and the road into C from the right, and together they separate everything. They pay nearly a third more than necessary because neither knows about the other. The cheapest three-way cut is B’s middle cut, costing 4, together with C’s isolating cut at C’s own roads, costing 9: it never pays for A’s roads at all, because once B’s side is cut away through the middle and C is cut off at the bottom, A is already alone with its two middle places. The shortcut kept A’s cut and dropped C’s because the two tie at 9, and on this network the tie went the expensive way.

The network was not chosen at random. It is the worst case found in a search over twenty thousand random sets of capacities on these fourteen roads: $17/13 = 1.308$, the largest ratio of shortcut to truth that search turned up.

Why the shortcut can never be worse than four thirds #

The guarantee has a proof that fits in a paragraph, and the figure below is that paragraph’s two columns.

Look at the cheapest three-way cut and at the three regions it leaves — the places coloured like A, like B and like C. The roads leaving A’s region are one way of cutting A off from the other two, so A’s cheapest isolating cut is no dearer than A’s region’s boundary; likewise for B and C. And every road of the three-way cut lies on the boundary of exactly two regions, since it joins two differently coloured places. So the three boundaries add up to exactly twice the cheapest cut, and the three isolating cuts add up to at most that.

Throwing away the dearest of three numbers keeps at most two thirds of their sum. So the two cheapest isolating cuts together cost at most $\tfrac23 \times 2 \times \text{OPT} = \tfrac43\,\text{OPT}$. With $k$ places instead of three, the same argument keeps $k - 1$ of $k$ cuts and gives $(1 - \tfrac1k) \times 2 = 2 - \tfrac2k$. On the drawn network the isolating cuts happen to equal the boundaries exactly — $9$, $8$ and $9$, adding to $26 = 2 \times 13$ — so nothing is lost in the first inequality, and all the loss is in combining two cuts that could have shared roads.

The argument never finds the cheapest cut. It uses the cheapest cut’s existence to show that three computable numbers, one per place, cannot add up to much more than twice it. It is the same move as the duality that bounds a network’s flow by any cut, made with a cut that nobody has computed.

How far the shortcut strays in practice #

The guarantee is a worst case. On most networks the shortcut does much better.

On two thousand random versions of the same network the shortcut was exactly right 98 per cent of the time, and when it was wrong it was wrong by at most a quarter. The cases where it fails are the ones like the drawn network, where the cheapest three-way cut reuses one separation’s roads for another and the isolating cuts, each optimising alone, cannot see the saving. Random capacities rarely line up to make that sharing worth much. Of the thirty-two misses, twenty-eight were off by at most a tenth, and only four by more than fifteen per cent.

This is the usual relation between a guarantee and a census, and it runs in both directions. The census cannot show the guarantee — two thousand networks of one shape are not all networks — and the guarantee does not predict the census: a method that is typically exact and occasionally a third out is described by “at most 4/3” as accurately as a method that is always a third out.

Why pairwise answers do not add up #

It is tempting to hope that the three-way cut is determined by the pairwise cuts, the fifteen numbers the Gomory–Hu tree holds for a network of six. It is not, and the reason is the sharing that defeats the shortcut.

The cheapest cut between A and B is at most the three-way cut, since the three-way cut separates A from B among other things; the same for the other two pairs. So the largest pairwise cut is a lower bound on the three-way cut. The sum of the pairwise cuts is an upper bound in a weaker sense — removing all three pairwise cuts together certainly separates everything — but it counts shared roads twice or three times. The truth can lie anywhere between, depending on how the pairwise cuts overlap, and nothing in the tree records overlaps: it records values, and the three-way cut is a question about which roads.

That is also why the multiway problem is hard where the pairwise one is not. A two-place cut is the answer to a flow problem, and flows have the property that the corners of their linear programs are whole numbers, so the relaxation and the problem agree. For three or more places the natural relaxation has fractional corners — the situation of corners that stop being whole — and the gap between the fractional answer and the true one is exactly what the multiway problem is about.

Where three-way cuts turn up #

The problem was first written down for computers. Harold Stone showed in 1977 that assigning the parts of a program to two processors — each part cheaper to run on one than the other, and each pair of communicating parts costing something if they are separated — is exactly a cheapest two-sided cut, with the processors as the two marked places. With three processors it is a three-way cut, and that was one of the problems the 1994 paper settled as hard.

It turned up again, more visibly, in pictures. Dividing a photograph into regions — sky, grass, road — can be posed as choosing a label for every pixel, where each pixel has a cost for each label according to its colour and each pair of neighbouring pixels pays a penalty if their labels differ. With two labels that is a two-sided cut, solved exactly by a flow, and for years it was the standard way to cut an object out of its background. With three or more labels it is a multiway cut in disguise, and Yuri Boykov, Olga Veksler and Ramin Zabih showed in 2001 both that it is hard and that a method close in spirit to the shortcut here — improve the labelling by repeatedly letting one label expand at a time, each step an exact two-sided cut — is never worse than twice the best. The shortcut on this page and the label-expansion method are both ways of doing the hard problem with repeated calls to the easy one.

What the pictures cannot show #

Anything larger. Every cut here is found by trying all $3^5$ colourings of one eight-place network, which is complete for that network and impossible for a network of a thousand places, where there are $3^{997}$. The figures certify the answers they draw and nothing about how the answer could be found at scale.

The hardness. That the three-way problem admits no efficient exact method unless a great many other problems do is the 1994 theorem, proved by encoding other hard problems as networks, and no picture of one network bears on it.

Why the census is so kind. The two thousand networks share one arrangement of roads and differ only in capacities from one to five. A network built to defeat the shortcut — many lettered places, each with cheap-looking private roads and an expensive shared middle — would fare far worse than any of them, and the census’s 98 per cent is a fact about this arrangement and this range of capacities, not about networks in general.

The worst case. The drawn network reaches $1.308$ and the census $1.250$; neither reaches $4/3$. Whether the bound is attained on networks of some other shape is a separate question — for large $k$ the $2 - 2/k$ bound is known to be approached — and the figures, confined to fourteen roads, cannot say.

Still open: what each added place costs #

For three places the question of how well the linear relaxation can be rounded has an exact answer. The relaxation of Gruia Călinescu, Howard Karloff and Yuval Rabani from 1998, which lets each place be split fractionally among the sides, was shown by David Karger, Philip Klein, Clifford Stein, Mikkel Thorup and Neal Young in 2004 to overstate the truth by a factor of up to $12/11$ on three-place networks, and Kevin Cheung, William Cunningham and Lawrence Tang found a rounding in 2006 that never loses more than $12/11$. The fractional three-way split and the whole one are, at worst, eleven twelfths apart, and that is settled.

With each place added the answer reopens. For four places the exact worst ratio of the relaxation is not pinned down, and as the number of places grows the known bounds spread apart — the best rounding and the worst known example have been approaching each other for twenty years, from both sides, without meeting, and the essay on the Gomory–Hu tree records where they stand. The shortcut on this page, at $2 - 2/k$, is the simplest guarantee of all and the weakest; everything better comes from the relaxation, and the question of how much better is, beyond three places, still open. What makes it hard is visible even in the eight-place network drawn here: the saving a cheap method misses is the sharing of roads between separations, and the number of ways separations can share grows with every place added.