Gomory–Hu tree

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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 | V | − 1 minimum cut computations.

Definition[edit]

Let G = ((VG, EG), 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, tVG.
Let T = (VT,ET) be a tree with VT = VG, denote the set of edges in an s-t path by Pst for each s,tVT.

Then T is said to be a Gomory–Hu tree of G if

λst = mine∈Pst c(Se, Te) for all s, tVG,

where

  1. Se and Te are the two connected components of T∖{e} in the sense that (Se, Te) form a s-t cut in G, and
  2. c(Se, Te) is the capacity of the cut in G.

Algorithm[edit]

Gomory–Hu Algorithm

Input: A weighted undirected graph G = ((VG, EG), c).
Output: A Gomory–Hu Tree T = (VT, ET).
1. Set VT = {VG} and ET = ∅.
2. Choose some XVT with | X | ≥ 2 if such X exists. Otherwise, go to step 6.
3. For each connected component C = (VC, EC) in TX. Let SC = ∪vT∈VC vT. Let S = { SC | C is a connected component in TX}.
    Contract the components to form G' = ((VG', EG'), c'), where
VG' = XS.
EG' = EG|X×X ∪ {(u, SC) ∈ X×S | (u,v)∈EG for some vSC}.
c' : VG'×VG'R+ is the capacity function defined as,
  1. if (u,SC)∈EG|X×S, c'(u,SC) = Σv∈SC:(u,v)∈EGc(u,v),
  2. c'(u,v) = c(u,v) otherwise.
4. Choose two vertices s, tX and find a minimum s-t cut (A',B') in G'.
    Set A = (∪SCA'∩S SC) ∪ (A' ∩ X) and B = (∪SCB'∩S SC) ∪ (B' ∩ X).
5. Set VT = (VTX) ∪ {AX, BX}.
    For each e = (X, Y) ∈ ET do
If YA, set e' = (AX, Y), else set e' = (BX, Y).
Set ET = (ET∖{e}) ∪ {e'} and w(e') = w(e).
    Set ET = ET ∪ {(AX, BX)}.
    Set w((AX, BX)) = c'(A', B').
    Go to step 2.
6. Replace each {v} ∈ VT by v and each ({u},{v}) ∈ ET by (u,v). Output T.

Analysis[edit]

Using the submodular property of the capacity function c, one has

c(X) + c(Y) ≥ c(XY) + c(XY).

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, tX.

To show that for all (P, Q) ∈ ET, w(P,Q) = λpq for some pP, qQ throughout the algorithm, one makes use of the following Lemma,

For any i, j, k in VG, λ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[edit]

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
Gomory–Hu G.svg Gomory–Hu T.svg
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. Gomory–Hu Gp1.svg Gomory–Hu T1.svg
3. Since TX = ∅, 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 = (VTX) ∪ {AX, BX} = { {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. Gomory–Hu Gp2.svg Gomory–Hu T2.svg
3. {0, 1, 2, 4} is the connected component in TX 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 = (VTX) ∪ {AX, BX} = { {0, 1, 2, 4}, {3}, {5} }.
    Since (X, {0, 1, 2, 4}) ∈ ET and {0, 1, 2, 4} ⊂ A, replace it with (AX, 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. Gomory–Hu Gp3.svg Gomory–Hu T3.svg
3. { {3}, {5} } is the connected component in TX 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,vX.
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 = (VTX) ∪ {AX, BX} = { {3}, {5}, {1, 4}, {0, 2} }.
    Since (X, {3}) ∈ ET and {3} ⊂ A, replace it with (AX, 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. Gomory–Hu Gp4.svg Gomory–Hu T4.svg
3. { {3}, {5} }, { {0, 2} } are the connected components in TX 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,vX.
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 = (VTX) ∪ {AX, BX} = { {3}, {5}, {0, 2}, {1}, {4} }.
    Since (X, {3}) ∈ ET and {3} ⊂ A, replace it with (AX, Y) = ({1}, {3}).
    Since (X, {0, 2}) ∈ ET and {0, 2} ⊂ B, replace it with (BX, 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. Gomory–Hu Gp5.svg Gomory–Hu T5.svg
3. { {1}, {3}, {4}, {5} } is the connected component in TX 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 = (VTX) ∪ {AX, BX} = { {3}, {5}, {1}, {4}, {0}, {2} }.
    Since (X, {4}) ∈ ET and {4} ⊂ B, replace it with (BX, 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 XVT with | X | ≥ 2. Hence, go to step 6.
6.
Gomory–Hu output.svg
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[edit]

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.

Andrew V. Goldberg and K. Tsioutsiouliklis implemented the Gomory-Hu algorithm and Gusfield algorithm. Experimental results comparing these algorithms are reported in[2] Source code is available here.

Cohen et al.[3] reports results on two parallel implementations of Gusfield's algorithm using OpenMP and MPI, respectively. Source code of these implementations is available here: Parallel Cut Tree Algorithms Page.

History[edit]

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

See also[edit]

References[edit]

  1. ^ R. E. Gomory, T. C. Hu. Multi-terminal network flows. Journal of the Society for Industrial and Applied Mathematics, vol. 9, 1961.
  2. ^ Goldberg, A. V.; Tsioutsiouliklis, K. (2001). "Cut Tree Algorithms: An Experimental Study". Journal of Algorithms 31 (1): 51–83. 
  3. ^ Cohen, J.; L. A. Rodrigues, F. Silva, R. Carmo, A. Guedes, E. P. Duarte Jr. (2011). "Parallel Implementations of Gusfield's Cut Tree Algorithm". Lecture Notes in Computer Science (LNCS). 7016 (Springer) (11th International Conference Algorithms and Architectures for Parallel Processing (ICA3PP)). ISSN 0302-9743. 
  • Dan Gusfield (1990). "Very Simple Methods for All Pairs Network Flow Analysis". SIAM J. Comput. 19 (1): 143–155. doi:10.1137/0219009. 
  • 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.