Gomory–Hu tree
Encyclopedia
In combinatorial optimization
Combinatorial optimization
In applied mathematics and theoretical computer science, combinatorial optimization is a topic that consists of finding an optimal object from a finite set of objects. In many such problems, exhaustive search is not feasible...

, the Gomory–Hu tree of an undirected graph with capacities is a weighted tree
Tree (graph theory)
In mathematics, more specifically graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles is a tree...

 that consists of edges representing all pairs minimum s-t cut in the graph. The Gomory–Hu tree can be constructed in | V | − 1 times minimum cut
Minimum cut
In graph theory, a minimum cut of a graph is a cut whose cutset has the smallest number of elements or smallest sum of weights possible...

 computation.

Definition

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

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

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

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 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.
align="left" colspan="2" |
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 ( , ) 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.
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.

Implementation

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.

History

The Gomory–Hu tree was introduced by R. E. Gomory
Ralph E. Gomory
Ralph Edward Gomory is an American applied mathematician and executive. Gomory worked at IBM as a researcher and later as an executive. During that time, his research led to the creation of new areas of applied mathematics....

and T. C. Hu in 1961.
The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.
 
x
OK