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 \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 s-t path by P_{st} for each s,t \in V_G. Then T is said to be a Gomory–Hu tree of G, if for each s, t \in V_G : \lambda_{st} = \min_{e\in P_{st}} 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 s-t cut in G.
2. c(S_e, T_e) is the capacity of the (S_e,T_e) 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}, \ E_T = \empty.
2. Choose some X \in V_T with ≥ 2 if such X 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.
4. :Let S = { S_C \mid C \text{ is a connected component in } T \setminus X }.
5. : Contract the components to form G' = ((V_{G'}, E_{G'}), c'), where: \begin{align} 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{align}
6. ::c':V_{G'} \times V_{G'} \to R^+ is the capacity function, defined as: \begin{align} &\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{align}
7. Choose two vertices s, t ∈ X and find a minimum s-t cut (A′, B′) in G'.
8. :Set A = \Biggl(\bigcup_{S_C \in A' \cap S} !!! S_C ! \Biggr) \cup (A' \cap X),\ B = \Biggl(\bigcup_{S_C \in B' \cap S} !!! S_C ! \Biggr) \cup (B' \cap X).
9. Set V_T = (V_T \setminus X) \cup {A \cap X, B \cap X }.
10. :For each e = (X, Y) \in E_T do:
11. :#Set e' = (A \cap X,Y) if Y \subset A, otherwise set e' = (B \cap X,Y).
12. :#Set E_T = (E_T \setminus {e}) \cup {e'}.
13. :#Set w(e') = w(e).
14. :Set E_T = E_T \cup {(A \cap X,\ B \cap X) }.
15. :Set w((A \cap X, B \cap X)) = c'(A', B').
16. :Go to step 2.
17. Replace each {v} \in V_T by v and each ({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) \ge 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) \in E_T, 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, \lambda_{ik} \ge \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.

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.{{cite journal

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.{{cite conference | editor1-last = Xiang | editor1-first = Yang | editor2-last = Cuzzocrea | editor2-first = Alfredo | editor3-last = Hobbs | editor3-first = Michael | editor4-last = Zhou | editor4-first = Wanlei

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.{{cite journal

References

References

1. (1961). "Multi-terminal network flows". Journal of the Society for Industrial and Applied Mathematics.
2. Goldberg, A. V.. (2001). "Cut Tree Algorithms: An Experimental Study". Journal of Algorithms.