Gomory–Hu tree

In combinatorial optimization, the Gomory–Hu tree of an undirected graph with capacities is a weighted tree that consists of edges representing all pairs minimum s-t cut in the graph. The Gomory–Hu tree can be constructed in | V | - 1 times minimum cut computation.

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: An 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'), where

V_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 do

If 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.

	G'	T
	1. Set VT = {VG} = { {0, 1, 2, 3, 4, 5} } and ET = ∅. 2. Since VT has only one vertex, choose X = VG = {1, 2, 3, 4, 5, 6}. Note that | X | = 6 ≥ 2.
1.
	3. Since T∖X = ∅, there is no contraction and therefore G' = G. 4. Choose s = 1 and t = 5. The minimum s-t cut (A', B') is ({0, 1, 2, 4}, {3, 5}) with c'(A', B') = 6.     Set A = {0, 1, 2, 4} and B = {3, 5}. 5. Set VT = (VT∖X) ∪ {A ∩ X, B ∩ X} = { {0, 1, 2, 4}, {3, 5} }.     Set ET = { ({0, 1, 2, 4}, {3, 5}) }.     Set w( ({0, 1, 2, 4}, {3, 5}) ) = c'(A', B') = 6.     Go to step 2. 2. Choose X = {3, 5}. Note that | X | = 2 ≥ 2.
2.
	3. {0, 1, 2, 4} is the connected component in T∖X and thus S = { {0, 1, 2, 4} }.     Contract {0, 1, 2, 4} to form G', where c'( (3, {0, 1, 2 ,4}) ) = c( (3, 1) ) + c( (3, 4) ) = 4. c'( (5, {0, 1, 2, 4}) ) = c( (5, 4) ) = 2. c'( (3, 5)) = c( (3, 5) ) = 6. 4. Choose s = 3, t = 5. The minimum s-t cut (A', B') in G' is ( {{0, 1, 2, 4}, 3}, {5} ) with c'(A', B') = 8.     Set A = {0, 1, 2, 3, 4} and B = {5}. 5. Set VT = (VT∖X) ∪ {A ∩ X, B ∩ X} = { {0, 1, 2, 4}, {3}, {5} }.     Since (X, {0, 1, 2, 4}) ∈ ET and {0, 1, 2, 4} ⊂ A, replace it with (A ∩ X, Y) = ({3}, {0, 1, 2 ,4}).     Set ET = { ({3}, {0, 1, 2 ,4}), ({3}, {5}) } with w(({3}, {0, 1, 2 ,4})) = w((X, {0, 1, 2, 4})) = 6. w(({3}, {5})) = c'(A', B') = 8.     Go to step 2. 2. Choose X = {0, 1, 2, 4}. Note that | X | = 4 ≥ 2.
3.
	3. { {3}, {5} } is the connected component in T∖X and thus S = { {3, 5} }.     Contract {3, 5} to form G', where c'( (1, {3, 5}) ) = c( (1, 3) ) = 3. c'( (4, {3, 5}) ) = c( (4, 3) ) + c( (4, 5) ) = 3. c'(u,v) = c(u,v) for all u,v ∈ X. 4. Choose s = 1, t = 2. The minimum s-t cut (A', B') in G' is ( {1, {3, 5}, 4}, {0, 2} ) with c'(A', B') = 6.     Set A = {1, 3, 4, 5} and B = {0, 2}. 5. Set VT = (VT∖X) ∪ {A ∩ X, B ∩ X} = { {3}, {5}, {1, 4}, {0, 2} }.     Since (X, {3}) ∈ ET and {3} ⊂ A, replace it with (A ∩ X, Y) = ({1, 4}, {3}).     Set ET = { ({1, 4}, {3}), ({3}, {5}), ({0, 2}, {1, 4}) } with w(({1, 4}, {3})) = w((X, {3})) = 6. w(({0, 2}, {1, 4})) = c'(A', B') = 6.     Go to step 2. 2. Choose X = {1, 4}. Note that | X | = 2 ≥ 2.
4.
	3. { {3}, {5} }, { {0, 2} } are the connected components in T∖X and thus S = { {0, 2}, {3, 5} }.     Contract {0, 2} and {3, 5} to form G', where c'( (1, {3, 5}) ) = c( (1, 3) ) = 3. c'( (4, {3, 5}) ) = c( (4, 3) ) + c( (4, 5) ) = 3. c'( (1, {0, 2}) ) = c( (1, 0) ) + c( (1, 2) ) = 2. c'( (4, {0, 2}) ) = c( (4, 2) ) = 4. c'(u,v) = c(u,v) for all u,v ∈ X. 4. Choose s = 1, t = 4. The minimum s-t cut (A', B') in G' is ( {1, {3, 5}}, {{0, 2}, 4} ) with c'(A', B') = 7.     Set A = {1, 3, 5} and B = {0, 2, 4}. 5. Set VT = (VT∖X) ∪ {A ∩ X, B ∩ X} = { {3}, {5}, {0, 2}, {1}, {4} }.     Since (X, {3}) ∈ ET and {3} ⊂ A, replace it with (A ∩ X, Y) = ({1}, {3}).     Since (X, {0, 2}) ∈ ET and {0, 2} ⊂ B, replace it with (B ∩ X, Y) = ({4}, {0, 2}).     Set ET = { ({1}, {3}), ({3}, {5}), ({4}, {0, 2}), ({1}, {4}) } with w(({1}, {3})) = w((X, {3})) = 6. w(({4}, {0, 2})) = w((X, {0, 2})) = 6. w(({1}, {4})) = c'(A', B') = 7.     Go to step 2. 2. Choose X = {0, 2}. Note that | X | = 2 ≥ 2.
5.
	3. { {1}, {3}, {4}, {5} } is the connected component in T∖X and thus S = { {1, 3, 4, 5} }.     Contract {1, 3, 4, 5} to form G', where c'( (0, {1, 3, 4, 5}) ) = c( (0, 1) ) = 1. c'( (2, {1, 3, 4, 5}) ) = c( (2, 1) ) + c( (2, 4) ) = 5. c'( (0, 2) ) = c( (0, 2) ) = 7. 4. Choose s = 0, t = 2. The minimum s-t cut (A', B') in G' is ( {0}, {2, {1, 3, 4, 5}} ) with c'(A', B') = 8.     Set A = {0} and B = {1, 2, 3 ,4 ,5}. 5. Set VT = (VT∖X) ∪ {A ∩ X, B ∩ X} = { {3}, {5}, {1}, {4}, {0}, {2} }.     Since (X, {4}) ∈ ET and {4} ⊂ B, replace it with (B ∩ X, Y) = ({2}, {4}).     Set ET = { ({1}, {3}), ({3}, {5}), ({2}, {4}), ({1}, {4}), ({0}, {2}) } with w(({2}, {4})) = w((X, {4})) = 6. w(({0}, {2})) = c'(A', B') = 8.     Go to step 2. 2. There does not exist X∈VT with | X | ≥ 2. Hence, go to step 6.
6.
	6. Replace VT = { {3}, {5}, {1}, {4}, {0}, {2} } by {3, 5, 1, 4, 0, 2}.     Replace ET = { ({1}, {3}), ({3}, {5}), ({2}, {4}), ({1}, {4}), ({0}, {2}) } by { (1, 3), (3, 5), (2, 4), (1, 4), (0, 2) }.     Output T. Note that exactly | V | - 1 = 6 - 1 = 5 times min-cut computation is performed.

Implementation

The 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.

History

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

See also

• Cut (graph theory)
• Max-flow min-cut theorem
• Maximum flow problem

References

• Dan Gusfield (1990). "Very Simple Methods for All Pairs Network Flow Analysis". SIAM J. Comput. 19 (1): 143–155.
• B. H. Korte, Jens Vygen (2008). "8.6 Gomory–Hu Trees". Combinatorial Optimization: Theory and Algorithms (Algorithms and Combinatorics, 21). Springer Berlin Heidelberg. pp. 180–186. ISBN 978-3-540-71844-4.