Gomory–Hu tree

Definition

Let G = ((V_G, E_G), c) be an undirected graph with c(u,v) being the capacity of the edge (u,v) respectively.

Denote the minimum capacity of an s-t cut by λ_st for each s, t ∈ V_G.Let T = (V_T,E_T) be a tree with V_T = V_G, denote the set of edges in an s-t path by P_st for each s,t ∈ V_T.

Then T is said to be a Gomory–Hu tree of G if

λ_st = min_e∈Pst c(S_e, T_e) for all s, t ∈ V_G,

where

1. S_e and T_e are the two connected components of T∖{e} in the sense that (S_e, T_e) form a s-t cut in G, and
2. c(S_e, T_e) is the capacity of the cut in G.

Algorithm

Gomory–Hu Algorithm

Input: A weighted undirected graph G = ((V_G, E_G), c)Output: A Gomory–Hu Tree T = (V_T, E_T).1. Set V_T = {V_G} and E_T = ∅.2. Choose some X∈V_T with | X | ≥ 2 if such X exists. Otherwise, go to step 6.3. For each connected component C = (V_C, E_C) in T∖X. Let S_C = ∪_vT∈VC v_T. Let S = { S_C | C is a connected component in T∖X}.    Contract the components to form G' = ((V_G', E_G'), c'), whereV_G' = X ∪ S.E_G' = E_G|_X×X ∪ {(u, S_C) ∈ X×S | (u,v)∈E_G for some v∈S_C}.c' : V_G'×V_G'→R⁺ is the capacity function defined as,

1. if (u,S_C)∈E_G|_X×S, c'(u,S_C) = Σ_{v∈SC:(u,v)∈EG}c(u,v),
2. c'(u,v) = c(u,v) otherwise.

4. Choose two vertices s, t ∈ X and find a minimum s-t cut (A',B') in G'.    Set A = (∪_SC∈A'∩S S_C) ∪ (A' ∩ X) and B = (∪_SC∈B'∩S S_C) ∪ (B' ∩ X).5. Set V_T = (V_T∖X) ∪ {A ∩ X, B ∩ X}.    For each e = (X, Y) ∈ E_T doIf Y⊂A, set e' = (A ∩ X, Y), else set e' = (B ∩ X, Y).Set E_T = (E_T∖{e}) ∪ {e'} and w(e') = w(e).    Set E_T = E_T ∪ {(A∩X, B∩X)}.    Set w((A∩X, B∩X)) = c'(A', B').    Go to step 2.6. Replace each {v} ∈ V_T by v and each ({u},{v}) ∈ E_T by (u,v). Output T.

Analysis

Using the submodular property of the capacity function c, one has

c(X) + c(Y) ≥ c(X ∩ Y) + c(X ∪ Y).

Then it can be shown that the minimum s-t cut in G' is also a minimum s-t cut in G for any s, t ∈ X.

To show that for all (P, Q) ∈ E_T, w(P,Q) = λ_pq for some p ∈ P, q ∈ Q throughout the algorithm, one makes use of the following Lemma,

For any i, j, k in V_G, λ_ik ≥ min(λ_ij, λ_jk).

The Lemma can be used again repeatedly to show that the output T satisfies the properties of a Gomory–Hu Tree.

Example

The following is a simulation of the Gomory–Hu's algorithm, where

1. green circles are vertices of T.
2. red and blue circles are the vertices in G'.
3. grey vertices are the chosen s and t.
4. red and blue coloring represents the s-t cut.
5. dashed edges are the s-t cut-set.
6. A is the set of vertices circled in red and B is the set of vertices circled in blue.

Implementations: Sequential and Parallel

Gusfield's algorithm can be used to find a Gomory–Hu tree without any vertex contraction in the same running time-complexity, which simplifies the implementation of constructing a Gomory–Hu Tree.

Andrew V. Goldberg and K. Tsioutsiouliklis implemented the Gomory-Hu algorithm and Gusfield algorithm. Experimental results comparing these algorithms are reported in Source code is available here.

Cohen et al. reports results on two parallel implementations of Gusfield's algorithm using OpenMP and MPI, respectively. Source code of these implementations is available here: Parallel Cut Tree Algorithms Page. (broken link)

History

The Gomory–Hu tree was introduced by R. E. Gomory and T. C. Hu in 1961.

Related concepts

In planar graphs, the Gomory–Hu tree is dual to the minimum weight cycle basis, in the sense that the cuts of the Gomory–Hu tree are dual to a collection of cycles in the dual graph that form a minimum-weight cycle basis.