Gomory–Hu tree explained

In combinatorial optimization, the Gomory–Hu tree^[1] 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 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 - cut by

λ _{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 - path by P _{st} for each s,t \in V _{G} .Then is said to be a Gomory–Hu tree of, if for each s, t \in V _{G}

$\backslash lambda\_\; =\; \backslash min\_\; c(S\_e,\; T\_e),$where

S _{e,} T _{e} \subseteq V _{G} are the two connected components of T \setminus \{e\} , and thus (S _{e,} T _{e)} forms an - cut in .c(S _{e,} T _{e)} is the capacity of the (S _{e,T} _{e)} cut in .

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.

1. Choose some

X \in V _{T} with if such exists. Otherwise, go to step 6.

1. For each connected component

C = (V _{C,E} _{C)} \in T \setminus X, let $S\_C\; =\; \backslash bigcup\_\; v\_T.$

Let

S = \{ S _{C} \mid C isaconnectedcomponentin T \setminus X \}.

Contract the components to form

G' = ((V _{G'} , E _{G'} ), c'), where:c':V _{G'} x V _{G'} \to R ^{+} is the capacity function, defined as:

1. Choose two vertices and find a minimum cut in .

Set

A = l ( c up _{S _{C} \in A' \cap S} S _{C} r ) \cup (A' \cap X), B = l ( c up _{S _{C} \in B' \cap S} S _{C} r ) \cup (B' \cap X).

1. 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' = (A \cap X,Y) if Y \subset A, otherwise set e' = (B \cap X,Y).

1. Set

E _{T} = (E _{T} \setminus \{e\}) \cup \{e'\}.

1. Set

w(e') = w(e).

Set

E _{T} = E _{T} \cup \{(A \cap X, B \cap X) \}.

Set

w((A \cap X, B \cap X)) = c'(A', B').

Go to step 2.

1. Replace each

\{v\} \in V _{T} by and each (\{u\},\{v\}) \in E _{T} by . Output .

Analysis

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

To show that for all

(P,Q) \in E _{T,} w(P,Q) = λ _{pq} for some, throughout the algorithm, one makes use of the following Lemma,

For any in,

λ _{ik} \ge min ( λ _{ij} , λ _{jk} ).

The Lemma can be used again repeatedly to show that the output 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.

Notes and References

1. Gomory . R. E. . Ralph E. Gomory . Hu . T. C. . T. C. Hu . Multi-terminal network flows . Journal of the Society for Industrial and Applied Mathematics . 9 . 4. 551–570 . 1961 . 10.1137/0109047 .
2. 10.1137/0219009 . Gusfield . Dan . Very Simple Methods for All Pairs Network Flow Analysis . SIAM J. Comput. . 19 . 1 . 143–155 . 1990.
3. Goldberg. A. V.. Tsioutsiouliklis, K.. Cut Tree Algorithms: An Experimental Study. Journal of Algorithms. 2001. 38. 1. 51–83. 10.1006/jagm.2000.1136 .
4. Cohen . Jaime . Rodrigues . Luiz A. . Silva . Fabiano . Carmo . Renato . Guedes . André Luiz Pires . Duarte . Jr., Elias P. . Xiang . Yang . Cuzzocrea . Alfredo . Hobbs . Michael . Zhou . Wanlei . Parallel implementations of Gusfield's cut tree algorithm . 10.1007/978-3-642-24650-0_22 . 258–269 . Springer . Lecture Notes in Computer Science . Algorithms and Architectures for Parallel Processing – 11th International Conference, ICA3PP, Melbourne, Australia, October 24–26, 2011, Proceedings, Part I . 7016 . 2011.
5. Hartvigsen . D. . Mardon . R. . 10.1137/S0895480190177042 . 3 . SIAM J. Discrete Math. . 403–418 . The all-pairs min cut problem and the minimum cycle basis problem on planar graphs . 7 . 1994. .