• Images
• Videos
• Documents
• Books
• Articles

Definition

Let G = ( V G , E G , c ) {\displaystyle G=(V_{G},E_{G},c)} be an undirected graph with c ( u , v ) {\displaystyle c(u,v)} being the capacity of the edge ( u , v ) {\displaystyle (u,v)} respectively.

Denote the minimum capacity of an s-t cut by λ s t {\displaystyle \lambda _{st}} for each s , t ∈ V G {\displaystyle s,t\in V_{G}} . Let T = ( V G , E T ) {\displaystyle T=(V_{G},E_{T})} be a tree, and denote the set of edges in an s-t path by P s t {\displaystyle P_{st}} for each s , t ∈ V G {\displaystyle s,t\in V_{G}} .

Then T is said to be a Gomory–Hu tree of G, if for each s , t ∈ V G {\displaystyle s,t\in V_{G}}

λ s t = min e ∈ P s t c ( S e , T e ) , {\displaystyle \lambda _{st}=\min _{e\in P_{st}}c(S_{e},T_{e}),}

where

1. S e , T e ⊆ V G {\displaystyle S_{e},T_{e}\subseteq V_{G}} are the two connected components of T ∖ { e } {\displaystyle T\setminus \{e\}} , and thus ( S e , T e ) {\displaystyle (S_{e},T_{e})} forms an s-t cut in G.
2. c ( S e , T e ) {\displaystyle c(S_{e},T_{e})} is the capacity of the ( S e , T e ) {\displaystyle (S_{e},T_{e})} cut in G.

Algorithm

Gomory–Hu Algorithm

Input: A weighted undirected graph G = ( ( V G , E G ) , c ) {\displaystyle G=((V_{G},E_{G}),c)} Output: A Gomory–Hu Tree T = ( V T , E T ) . {\displaystyle T=(V_{T},E_{T}).}

1. Set V T = { V G } ,   E T = ∅ . {\displaystyle V_{T}=\{V_{G}\},\ E_{T}=\emptyset .}
2. Choose some X ∈ V T {\displaystyle X\in V_{T}} with |X| ≥ 2 if such X exists. Otherwise, go to step 6.
3. For each connected component C = ( V C , E C ) ∈ T ∖ X , {\displaystyle C=(V_{C},E_{C})\in T\setminus X,} let S C = ⋃ v T ∈ V C v T . {\textstyle S_{C}=\bigcup _{v_{T}\in V_{C}}v_{T}.} Let S = { S C ∣ C  is a connected component in  T ∖ X } . {\displaystyle S=\{S_{C}\mid C{\text{ is a connected component in }}T\setminus X\}.} Contract the components to form G ′ = ( ( V G ′ , E G ′ ) , c ′ ) , {\displaystyle 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 } ∪ { ( S C 1 , S C 2 ) ∈ S × S ∣ ( u , v ) ∈ E G  for some  u ∈ S C 1  and  v ∈ S C 2 } {\displaystyle {\begin{aligned}V_{G'}&=X\cup S\\[2pt]E_{G'}&=E_{G}|_{X\times X}\cup \{(u,S_{C})\in X\times S\mid (u,v)\in E_{G}{\text{ for some }}v\in S_{C}\}\\[2pt]&\qquad \qquad \quad \!\cup \{(S_{C1},S_{C2})\in S\times S\mid (u,v)\in E_{G}{\text{ for some }}u\in S_{C1}{\text{ and }}v\in S_{C2}\}\end{aligned}}} c ′ : V G ′ × V G ′ → R + {\displaystyle c':V_{G'}\times V_{G'}\to R^{+}} is the capacity function, defined as: if    ( u , S C ) ∈ E G | X × S : c ′ ( u , S C ) = ∑ v ∈ S C : ( u , v ) ∈ E G c ( u , v ) if    ( S C 1 , S C 2 ) ∈ E G | S × S : c ′ ( S C 1 , S C 2 ) = ∑ ( u , v ) ∈ E G : u ∈ S C 1 ∧ v ∈ S C 2 c ( u , v ) otherwise : c ′ ( u , v ) = c ( u , v ) {\displaystyle {\begin{aligned}&{\text{if }}\ (u,S_{C})\in E_{G}|_{X\times S}:&&c'(u,S_{C})=\!\!\!\sum _{\begin{smallmatrix}v\in S_{C}:\\(u,v)\in E_{G}\end{smallmatrix}}\!\!\!c(u,v)\\[4pt]&{\text{if }}\ (S_{C1},S_{C2})\in E_{G}|_{S\times S}:&&c'(S_{C1},S_{C2})=\!\!\!\!\!\!\!\sum _{\begin{smallmatrix}(u,v)\in E_{G}:\\u\in S_{C1}\,\land \,v\in S_{C2}\end{smallmatrix}}\!\!\!\!\!c(u,v)\\[4pt]&{\text{otherwise}}:&&c'(u,v)=c(u,v)\end{aligned}}}
4. Choose two vertices s, t ∈ X and find a minimum s-t cut (A′, B′) in G'. Set A = ( ⋃ S C ∈ A ′ ∩ S S C ) ∪ ( A ′ ∩ X ) ,   {\displaystyle A={\Biggl (}\bigcup _{S_{C}\in A'\cap S}\!\!\!S_{C}\!{\Biggr )}\cup (A'\cap X),\ } B = ( ⋃ S C ∈ B ′ ∩ S S C ) ∪ ( B ′ ∩ X ) . {\displaystyle B={\Biggl (}\bigcup _{S_{C}\in B'\cap S}\!\!\!S_{C}\!{\Biggr )}\cup (B'\cap X).}
5. Set V T = ( V T ∖ X ) ∪ { A ∩ X , B ∩ X } . {\displaystyle V_{T}=(V_{T}\setminus X)\cup \{A\cap X,B\cap X\}.} For each e = ( X , Y ) ∈ E T {\displaystyle e=(X,Y)\in E_{T}} do:
   1. Set e ′ = ( A ∩ X , Y ) {\displaystyle e'=(A\cap X,Y)} if Y ⊂ A , {\displaystyle Y\subset A,} otherwise set e ′ = ( B ∩ X , Y ) . {\displaystyle e'=(B\cap X,Y).}
   2. Set E T = ( E T ∖ { e } ) ∪ { e ′ } . {\displaystyle E_{T}=(E_{T}\setminus \{e\})\cup \{e'\}.}
   3. Set w ( e ′ ) = w ( e ) . {\displaystyle w(e')=w(e).}
   Set E T = E T ∪ { ( A ∩ X ,   B ∩ X ) } . {\displaystyle E_{T}=E_{T}\cup \{(A\cap X,\ B\cap X)\}.} Set w ( ( A ∩ X , B ∩ X ) ) = c ′ ( A ′ , B ′ ) . {\displaystyle w((A\cap X,B\cap X))=c'(A',B').} Go to step 2.
6. Replace each { v } ∈ V T {\displaystyle \{v\}\in V_{T}} by v and each ( { u } , { v } ) ∈ E T {\displaystyle (\{u\},\{v\})\in 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 ) . {\displaystyle c(X)+c(Y)\geq c(X\cap Y)+c(X\cup 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 , {\displaystyle (P,Q)\in E_{T},} w ( P , Q ) = λ p q {\displaystyle w(P,Q)=\lambda _{pq}} for some p ∈ P, q ∈ Q throughout the algorithm, one makes use of the following lemma,

For any i, j, k in VG, λ i k ≥ min ( λ i j , λ j k ) . {\displaystyle \lambda _{ik}\geq \min(\lambda _{ij},\lambda _{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 = {0, 1, 2, 3, 4, 5}. 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', wherec'( (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}) } withw(({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', wherec'( (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}) } withw(({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', wherec'( (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}) } withw(({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', wherec'( (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}) } withw(({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.

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, and performed an experimental evaluation and comparison.³

Cohen et al. report results on two parallel implementations of Gusfield's algorithm using OpenMP and MPI, respectively.⁴

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

See also

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

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

References

1. Gomory, R. E.; Hu, T. C. (1961). "Multi-terminal network flows". Journal of the Society for Industrial and Applied Mathematics. 9 (4): 551–570. doi:10.1137/0109047. /wiki/Ralph_E._Gomory ↩

2. Gusfield, Dan (1990). "Very Simple Methods for All Pairs Network Flow Analysis". SIAM J. Comput. 19 (1): 143–155. doi:10.1137/0219009. /wiki/Doi_(identifier) ↩

3. Goldberg, A. V.; Tsioutsiouliklis, K. (2001). "Cut Tree Algorithms: An Experimental Study". Journal of Algorithms. 38 (1): 51–83. doi:10.1006/jagm.2000.1136. /wiki/Doi_(identifier) ↩

4. Cohen, Jaime; Rodrigues, Luiz A.; Silva, Fabiano; Carmo, Renato; Guedes, André Luiz Pires; Duarte, Jr., Elias P. (2011). "Parallel implementations of Gusfield's cut tree algorithm". In Xiang, Yang; Cuzzocrea, Alfredo; Hobbs, Michael; Zhou, Wanlei (eds.). Algorithms and Architectures for Parallel Processing – 11th International Conference, ICA3PP, Melbourne, Australia, October 24–26, 2011, Proceedings, Part I. Lecture Notes in Computer Science. Vol. 7016. Springer. pp. 258–269. doi:10.1007/978-3-642-24650-0_22. ISBN 978-3-642-24649-4.{{cite conference}}: CS1 maint: multiple names: authors list (link) 978-3-642-24649-4 ↩

5. Hartvigsen, D.; Mardon, R. (1994). "The all-pairs min cut problem and the minimum cycle basis problem on planar graphs". SIAM J. Discrete Math. 7 (3): 403–418. doi:10.1137/S0895480190177042.. /wiki/Doi_(identifier) ↩