One tree for every cut

The bottleneck is the whole story answers one question about a network: how much can travel from one chosen place to another, and which cheapest cut proves it — two numbers that have to meet, one bounding the other and equal to it at the best. A network of six places has fifteen such questions, one for each pair, and a network of a hundred places has 4,950. Answered one at a time, each needs its own flow and its own cut.

They do not need to be answered one at a time. The fifteen answers for the network below fit on a tree with five numbers.

The tree’s numbers are not the roads’ capacities. Its edges happen to run along roads in this network, but the road from A to D carries 2 and the tree puts 5 on that edge, and the road from A to B carries 4 where the tree says 6. What the tree records is not how much each road holds but how hard two places are to separate: the number on each tree edge is the cheapest cut between its two ends, and the cheapest cut between any two places is the weakest link on the tree’s path from one to the other.

Reading a cut off the tree #

Take B and E, one in each triangle. On the tree the path runs B to A to D to E, crossing the numbers 6, 5 and 10, so the tree says the cheapest cut between them is 5. And it is: removing the three roads between the triangles — A to D at 2, B to E at 1, C to F at 2 — separates every place on the left from every place on the right, for a total of 5.

That answer is not the obvious one. Cutting B off by itself costs its three roads, 4, 1 and 1, which is 6; cutting E off by itself costs 6, 3 and 1, which is 10. The cheapest way to separate B from E isolates neither of them, and the tree finds it because B and E lie on opposite sides of the edge marked 5.

Take D and E instead. The path is a single edge marked 10, which is the price of E’s own roads, and no cheaper division puts D on one side and E on the other. Take B and C: the path B to A to C crosses 6 and 8, so the answer is 6, which is B cut off alone. Every one of the fifteen answers is the minimum of a few numbers along a path, and a path in a tree is unique, so there is nothing to choose.

Fifteen cuts, checked against every cut #

A cheapest cut between two places is a set of places containing one and not the other, priced by the roads that leave it, and with six places there are exactly 16 such sets for each pair. So the fifteen answers can be found without any theorem, by trying all of them.

The table sets the exhaustive answer beside the tree’s answer for every pair, and they agree fifteen times. The side column shows the shape of the answers. Nine of the fifteen pairs have the same cheapest cut, the three roads between the triangles at a price of 5, and those are exactly the nine pairs with one place in each triangle. The other six cut a single place off: B for 6, C for 8, E for 10 and F for 9.

That is what the tree’s shape is saying. It has one edge marked 5 in the middle, with A and its neighbours on one side and D and its neighbours on the other, so it has found the two triangles and the weak joint between them. Inside each triangle the places hang from its best-connected member — A, whose roads total 11, and D, whose roads total 12 — and the numbers on those short edges are the prices of cutting the lesser places off.

Why a tree can hold them #

The fifteen numbers are not arbitrary, and the property that lets them sit on a tree can be stated in one line and seen in every row of a table.

Take any three places, $u$, $v$ and $w$, and the cheapest cuts between the three pairs. Any cut separating $u$ from $w$ must put $v$ on one side or the other, so it separates $v$ from $u$ or $v$ from $w$. Its price is therefore at least the smaller of those two cheapest cuts:

$$\lambda(u, w) \ge \min\bigl(\lambda(u, v),\ \lambda(v, w)\bigr).$$

Apply that to each of the three pairs in turn and the three numbers cannot have a unique smallest one. The two smallest are always equal. In all twenty triples of the six places they are, and in eighteen of them the shared smallest value is the 5 of the joint between the triangles, because only the two triangles themselves keep all three places on one side of it.

That is exactly the property of numbers read off a tree as path minima. On a tree, the paths between three places meet at a single junction, each edge of that configuration lies on the paths of exactly two of the three pairs, and so the smallest number anywhere on it is the minimum for at least two pairs. Conversely, a table of numbers with the two-smallest-equal property on every triple can always be realised as the path minima of some tree, and the cheapest cuts have the property for the reason above. What Gomory and Hu added was that a tree realising them can be built from the network’s own cuts, with a cut attached to every edge.

Five cuts build it #

The construction in the figure is Gusfield’s, from 1990, a simplification of the original that never merges places together. Start with every place hanging from A. Take the second place, B, find a cheapest cut between B and the place it hangs from, and write that cut’s price on the tree edge between them: 6, with B alone on its side. Nothing else was on B’s side, so nothing moves. C is cut from A in the same way, at 8, with C alone.

The third step is the one that shapes the tree. The cheapest cut between D and A is the joint between the triangles, price 5, and it puts D, E and F on D’s side. E and F come later in the list, are on D’s side, and still hang from A, so they are moved to hang from D instead. Then E and F are each cut from D, at 10 and at 9, each alone on its side.

Five cheapest cuts, one per place after the first, and the tree is complete. The remaining ten pairs never have a cut computed for them; their answers come out of the tree. The claim that they come out right is the Gomory–Hu theorem, and the table of fifteen pairs is it checked on this network.

The reason the reattachment step is safe is a property of cuts called submodularity: for any two sets of places, the prices of their intersection and their union together come to no more than the prices of the two sets themselves. It means that cheapest cuts can always be chosen so that they do not cross one another — any two either nest, or are disjoint, or together cover every place — and a family of cuts that never cross is exactly a family that can be drawn as the edges of a tree.

The tree is a network too #

Read the tree as a road network in its own right — five roads, with capacities 6, 8, 5, 10 and 9 — and ask the fifteen questions of it. In a network shaped like a tree there is only one route between any two places, so the most that can travel between them is the narrowest road on that route, and the cheapest cut is that road alone. Those are exactly the path minima. The five-road network gives the same fifteen answers as the nine-road one, and the argument takes a sentence, because in a tree the route is forced and so is the cut.

So for any question about how much can pass between two places, the original network can be thrown away and the tree kept, and nothing smaller would do: any network that keeps six places connected needs at least five roads, and a network with exactly five is a tree, which is why a tree on six places always has one edge fewer than its places. What the tree loses is everything else — which roads exist, how a flow actually runs, what happens when three places must be separated at once.

Nor is it the only tree that would do. There are 1,296 different trees on six labelled places, the number that sixteen trees on four points counts in the smallest interesting case, and several of them can carry numbers that reproduce the fifteen answers. In this network F could hang from E instead of from D, still marked 9: the path from D to F would then cross 10 and 9, the answer would still be 9, and none of the fifteen minima would change. That alternative is a genuine Gomory–Hu tree too, since the cheapest cut between F and E is 9. What the theorem promises is at least one tree whose edges both reproduce the numbers and name real cheapest cuts.

Strengthening one road #

The tree also says where extra capacity would count. Suppose the road from A to D is raised from 2 to 5. The joint between the triangles now costs 8, and redrawing the tree gives B to A at 6, C to A at 8, D to A at 8, E to D at 10 and F to D at 9: the middle edge has risen from 5 to 8 and nothing else has changed.

But the answer for B and E does not rise to 8. Their path now crosses 6, 8 and 10, so the cheapest cut between them is 6 — B cut off alone, its three roads unchanged at 4, 1 and 1. Six of the nine pairs across the triangles rise all the way to 8, and the three that involve B stop at 6, because separating B from anything was never going to cost more than B’s own roads.

Before the change, the tree already showed that this would happen. The edge from B to A was marked 6, a single unit above the joint, and every path from B to the other triangle runs through it. Whatever a reinforcement does to the joint, the answer for any pair can rise only as far as the next-weakest number on that pair’s path, and that number is on the tree before anything is built.

A reinforcement does not always move a single tree edge. Raising the road from B to E by one, from 1 to 2, changes three numbers at once — B to A becomes 7, the joint becomes 6, and E to D becomes 11 — because that road lies in B’s own cut, in E’s, and in the joint between the triangles. A road’s capacity counts in every cut that crosses it, and the tree shows which of those cuts were the cheapest.

Never more than five values #

A consequence can be read off before any network is drawn. A tree on six places has five edges, and every cheapest cut is the number on one of them, so the fifteen cheapest cuts of any six-place network take at most five different values. For a network of a hundred places, the 4,950 cheapest cuts take at most 99.

Across two hundred random networks, the number of distinct values runs from two to five and never reaches six. Fifteen numbers chosen by any other rule would not behave that way; fifteen arbitrary prices could all differ. The ceiling is a shadow of the tree, visible in the counts without drawing it, and the drawn network sits at the top of the range with all five values different.

A tree for cuts, and a tree for single routes #

There is an older tree that answers a different question about the same network, and the resemblance is instructive.

Suppose the question is not how much can travel between two places in total, spread over every route, but how wide the widest single route is — a route being only as wide as its narrowest road. That answer also lives on a tree: the tree that keeps the widest roads it can without closing a loop, the maximum spanning tree. The widest single route between two places is the narrowest road on the path between them in that tree, which is the same path-minimum rule applied to a different tree. The tree inside the triangulation builds the minimum version of that tree by the cut property, and the maximum version is the same construction read the other way.

The two trees generally differ, because the questions do. In the drawn network the widest single route from B to E is 2: the road between them carries 1, and every other route has to cross between the triangles on a road of capacity 2 or less. The total that can travel from B to E over every route at once is 5. One tree summarises the best single route and the other the best combination of routes, and that both kinds of answer sit on trees as path minima is a statement about how both quantities behave on triples of places.

Where the tree does not exist #

The roads must run both ways. The tree records one number for each pair and uses it in both directions. The single-pair theorem survives one-way roads, and so does its cousin Hall’s theorem, which is max-flow min-cut applied to a network of people and tasks; what does not survive is the sharing of cuts among pairs. For a network of one-way roads, the cheapest cut from $u$ to $v$ and from $v$ to $u$ can differ, the two-smallest-equal property fails, and no tree of this kind need exist.

The tree gives values and one cut per edge, not every cut. Each tree edge comes with a cheapest cut between its ends, and the cheapest cut between any other pair can be taken to be one of those five. But a pair may have several cheapest cuts of the same price, and the tree names one of them; the others are not recorded. The drawn network was chosen so that every pair’s cheapest cut is unique, which is why the side column in the table of pairs is unambiguous.

And the tree answers questions about pairs. Asking for the cheapest set of roads separating three or more places from one another at once is the question of when several pairs share the roads, and there the answer is on no tree: the cheapest separating cut can exceed any flow the places can exchange, and finding it is a harder problem in kind.

Six places, one order, and cuts shown already uncrossed #

Every network drawn has six places. With six places there are 16 cuts per pair and every cheapest cut can be found by trying them all, which is what makes the tables checks rather than claims. The theorem is about every undirected network; the drawings establish it on this one and on two hundred random ones.

The construction is drawn in one order. Gusfield’s method takes the places in a chosen order and can produce different trees in different orders. Every tree it produces gives the same path minima — the fifteen cheapest cuts do not depend on the order — but the shape of the tree can change, and the drawing shows only the tree for the order A to F.

And the uncrossing is described, not drawn. That cheapest cuts can be chosen never to cross is what makes a tree possible, and the figures show the result — five cuts that nest — without showing any cuts being uncrossed.

Still open: how nearly many places can be cut apart #

The tree ends where three places have to be separated at once. That problem is hard in general, and what can be done is to come close. Dahlhaus, Johnson, Papadimitriou, Seymour and Yannakakis observed in 1994 that the pairwise cuts already get within a factor of two: for each of $k$ places take the cheapest cut isolating it from all the others, discard the most expensive of these, and the rest together separate every place for at most $2 - 2/k$ times the cheapest possible price.

A relaxation that lets each place be divided fractionally among the sides does much better. For a single pair such relaxations cost nothing, because their corners are whole, as the corners of the assignment problem are; with three or more places to separate they are not, which is the situation of corners that stop being whole. Rounding it, Sharma and Vondrák reached a guarantee of about 1.2965 times the cheapest price, and constructions by Bérczi, Chandrasekaran, Király and Madan show that the same relaxation can overstate what is achievable by a factor of at least about 1.2 on some networks. If the Unique Games Conjecture holds — a hypothesis about approximation that has been neither proved nor refuted — the relaxation’s worst ratio is exactly the best guarantee any efficient method can give. Where between 1.2 and 1.2965 that ratio lies is not known, and it is the number that would settle how well many places can be cut apart.

Many answers from a few numbers #

Fifteen questions about a network had fifteen answers, and the answers were not independent: every three of them satisfied a rule that only numbers on a tree can satisfy. Once that rule is noticed, five numbers are enough to reconstruct all fifteen, and five cuts are enough to find the five numbers.

When many quantities are defined pairwise, check whether every triple has its two smallest equal. If it does, the whole table is a tree in disguise, and the tree is both the cheapest way to store the table and the clearest picture of what it says.