Existence of Gomory–Hu cut trees

Every symmetric submodular set function f on a nonempty finite vertex type has a cut tree: a weighted tree on the vertices in which the minimum cut value between any two distinct vertices is the minimum weight on the tree path between them, and deleting any tree edge leaves a minimum cut between its ends. Cut capacities of weighted graphs are the motivating instances, but only symmetry, submodularity and finiteness are used.

The construction is the contraction-free form of the Gomory–Hu construction. It grows a set R of representatives, keeping a tree on all vertices in which every vertex outside R is a leaf attached to a representative, and every edge between representatives leaves a minimum cut between its ends. To absorb a leaf x attached to r, the multi-cut non-crossing lemma supplies a minimum r–x cut crossing none of the cuts of tree edges between representatives. Every branch of the tree at r then lies on one side of this cut. The edge s(r, x) stays, and the branches on the side of x are moved from r to x; by the ultrametric inequality, the moved edges still leave minimum cuts. The sides of the new tree's edges are identified from which of its edges cross a given set, so no walks need to be transported between the two trees. Once every vertex is a representative, TauCeti.TerminalCut.IsCutTree.of_isMinimum_edgeSide gives the cut tree.

Main results

• TauCeti.TerminalCut.exists_isCutTree: the Gomory–Hu theorem for symmetric submodular set functions.

References

• R. E. Gomory and T. C. Hu, Multi-terminal network flows, J. SIAM 9 (1961), 551–570.
• D. Gusfield, Very Simple Methods for All Pairs Network Flow Analysis, SIAM J. Comput. 19 (1990), 143–155.
• B. Korte and J. Vygen, Combinatorial Optimization: Theory and Algorithms, Section 8.6.

One step of the construction

For a tree T, a leaf x attached to r, and the side X of a cut containing x but not r, the graph rewire T X r x keeps the edges of T away from r and the edge s(r, x), and attaches every other neighbour y of r to hub X r x y, which is x when y ∈ X and r otherwise.

The invariant and the induction

theorem TauCeti.TerminalCut.exists_isCutTree {V : Type u_1} {K : Type u_2} [Fintype V] [DecidableEq V] [AddCommMonoid K] [LinearOrder K] [IsOrderedCancelAddMonoid K] {f : Finset V → K} [Nonempty V] (hf : IsSymmSubmodular f) : ∃ (T : SimpleGraph V) (w : Sym2 V → K), IsCutTree f T w

Gomory–Hu theorem. Every symmetric submodular set function on a nonempty finite vertex type has a cut tree: a weighted tree on the vertices in which the minimum cut value between any two distinct vertices is the minimum weight on the tree path between them, and deleting any tree edge leaves a minimum cut between its ends.