Gomory–Hu tree

In combinatorial optimization, the Gomory–Hu tree of an undirected graph with capacities is a weighted tree that represents the minimum s-t cuts for all s-t pairs in the graph. The Gomory–Hu tree can be constructed in Template:Math maximum flow computations. It is named for Ralph E. Gomory and T. C. Hu.

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 Template:Mvar-Template:Mvar cut by ${\lambda }_{st}$ for each $s,t\in V_G$.

Let $T=(V_G,E_T)$ be a tree, and denote the set of edges in an Template:Mvar-Template:Mvar path by $P_{st}$ for each $s,t\in V_G$.

Then Template:Mvar is said to be a Gomory–Hu tree of Template:Mvar, if for each $s,t\in V_G$

${\lambda }_{st}=\underset{e\in P_{st}}{\min }c(S_e,T_e),$

where

1. $S_e,T_e\subseteq V_G$ are the two connected components of $T\setminus \{e\}$, and thus $(S_e,T_e)$ forms an Template:Mvar-Template:Mvar cut in Template:Mvar.
2. $c(S_e,T_e)$ is the capacity of the $(S_e,T_e)$ cut in Template:Mvar.

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\},E_T=\mathrm{\varnothing }.$
2. Choose some $X\in V_T$ with Template:Math if such Template:Mvar exists. Otherwise, go to step 6.
3. For each connected component $C=(V_C,E_C)\in T\setminus X,$ let $S_C=\bigcup _{v_T\in V_C}{v}_T.$

   Let $S=\{S_C\mid C\text{ is a connected component in }T\setminus X\}.$

   Contract the components to form $G^{\prime }=((V_{G^{\prime }},E_{G^{\prime }}),c^{\prime }),$ where:$$\begin{array}{cc}{V}_{G^{\prime }}& =X\cup S\\ E_{G^{\prime }}& =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\}\\ & \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{array}$$

   $c^{\prime }:V_{G^{\prime }}\times V_{G^{\prime }}\to R^{+}$ is the capacity function, defined as:$$\begin{array}{cccc}& \text{if }(u,S_C)\in E_G{|}_{X\times S}:& & c^{\prime }(u,S_C)=\sum _{\begin{array}{c}v\in S_C:\\ (u,v)\in E_G\end{array}}c(u,v)\\ & \text{if }(S_{C1},S_{C2})\in E_G{|}_{S\times S}:& & c^{\prime }(S_{C1},S_{C2})=\sum _{\begin{array}{c}(u,v)\in E_G:\\ u\in S_{C1}\wedge v\in S_{C2}\end{array}}c(u,v)\\ & \text{otherwise}:& & c^{\prime }(u,v)=c(u,v)\end{array}$$

4. Choose two vertices Template:Math and find a minimum Template:Math cut Template:Math in Template:Mvar.

   Set $A=\left(\bigcup _{S_C\in A^{\prime }\cap S}{S}_C\right)\cup (A^{\prime }\cap X),$$B=\left(\bigcup _{S_C\in B^{\prime }\cap S}{S}_C\right)\cup (B^{\prime }\cap X).$

5. Set $V_T=(V_T\setminus X)\cup \{A\cap X,B\cap X\}.$

   For each $e=(X,Y)\in E_T$ do:

   1. Set $e^{\prime }=(A\cap X,Y)$ if $Y\subset A,$ otherwise set $e^{\prime }=(B\cap X,Y).$
   2. Set $E_T=(E_T\setminus \{e\})\cup \{e^{\prime }\}.$
   3. Set $w(e^{\prime })=w(e).$

   Set $E_T=E_T\cup \{(A\cap X,B\cap X)\}.$

   Set $w((A\cap X,B\cap X))=c^{\prime }(A^{\prime },B^{\prime }).$

   Go to step 2.

6. Replace each $\{v\}\in V_T$ by Template:Mvar and each $(\{u\},\{v\})\in E_T$ by Template:Math. Output Template:Mvar.

Analysis

Using the submodular property of the capacity function Template:Mvar, one has $$c(X)+c(Y)\ge c(X\cap Y)+c(X\cup Y).$$ Then it can be shown that the minimum Template:Math cut in Template:Mvar is also a minimum Template:Math cut in Template:Mvar for any Template:Math.

To show that for all $(P,Q)\in E_T,$ $w(P,Q)={\lambda }_{pq}$ for some Template:Math, Template:Math throughout the algorithm, one makes use of the following lemma,

For any Template:Mvar in Template:Mvar, ${\lambda }_{ik}\ge \min ({\lambda }_{ij},{\lambda }_{jk}).$

The lemma can be used again repeatedly to show that the output Template:Mvar 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', 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.

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

References

• Template:Cite book