Gomory–Hu tree

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 {{mvar|s}}-{{mvar|t}} cut by $\backslash lambda\_\{st\}$ for each $s,\; t\; \backslash in\; V\_G$.

: Let $T\; =\; (V\_G,\; E\_T)$ be a tree, and denote the set of edges in an {{mvar|s}}-{{mvar|t}} path by $P\_\{st\}$ for each $s,t\; \backslash in\; V\_G$.

Then {{mvar|T}} is said to be a Gomory–Hu tree of {{mvar|G}}, if for each $s,\; t\; \backslash in\; V\_G$

: $\backslash lambda\_\{st\}\; =\; \backslash min\_\{e\backslash in\; P\_\{st\}\}\; c(S\_e,\; T\_e),$

where

1. $S\_e,\; T\_e\; \backslash subseteq\; V\_G$ are the two connected components of $T\; \backslash setminus\; \backslash \{e\backslash \}$, and thus $(S\_e,\; T\_e)$ forms an {{mvar|s}}-{{mvar|t}} cut in {{mvar|G}}.
2. $c(S\_e,\; T\_e)$ is the capacity of the $(S\_e,T\_e)$ cut in {{mvar|G}}.

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\; =\; \backslash \{V\_G\backslash \},\; \backslash \; E\_T\; =\; \backslash empty.$
2. Choose some $X\; \backslash in\; V\_T$ with {{math|{{abs|X}} ≥ 2}} if such {{mvar|X}} exists. Otherwise, go to step 6.
3. For each connected component $C\; =\; (V\_C,E\_C)\; \backslash in\; T\; \backslash setminus\; X,$ let $S\_C\; =\; \backslash bigcup\_\{v\_T\; \backslash in\; V\_C\}\; v\_T.$
4. :Let $$

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

1. : Contract the components to form $G\text{'}\; =\; ((V\_\{G\text{'}\},\; E\_\{G\text{'}\}),\; c\text{'}),$ 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}

1. ::$c\text{'}:V\_\{G\text{'}\}\; \backslash times\; V\_\{G\text{'}\}\; \backslash 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}

1. Choose two vertices {{math|s, t ∈ X}} and find a minimum {{math|s-t}} cut {{math|(A′, B′)}} in {{mvar|G'}}.
2. :Set $A\; =\; \backslash Biggl(\backslash bigcup\_\{S\_C\; \backslash in\; A\text{'}\; \backslash cap\; S\}\; \backslash !\backslash !\backslash !\; S\_C\; \backslash !\; \backslash Biggr)\; \backslash cup\; (A\text{'}\; \backslash cap\; X),\backslash$$B\; =\; \backslash Biggl(\backslash bigcup\_\{S\_C\; \backslash in\; B\text{'}\; \backslash cap\; S\}\; \backslash !\backslash !\backslash !\; S\_C\; \backslash !\; \backslash Biggr)\; \backslash cup\; (B\text{'}\; \backslash cap\; X).$
3. Set $V\_T\; =\; (V\_T\; \backslash setminus\; X)\; \backslash cup\; \backslash \{A\; \backslash cap\; X,\; B\; \backslash cap\; X\; \backslash \}.$

1. :For each $e\; =\; (X,\; Y)\; \backslash in\; E\_T$ do:
2. :#Set $e\text{'}\; =\; (A\; \backslash cap\; X,Y)$ if $Y\; \backslash subset\; A,$ otherwise set $e\text{'}\; =\; (B\; \backslash cap\; X,Y).$
3. :#Set $E\_T\; =\; (E\_T\; \backslash setminus\; \backslash \{e\backslash \})\; \backslash cup\; \backslash \{e\text{'}\backslash \}.$
4. :#Set $w(e\text{'})\; =\; w(e).$
5. :Set $E\_T\; =\; E\_T\; \backslash cup\; \backslash \{(A\; \backslash cap\; X,\backslash \; B\; \backslash cap\; X)\; \backslash \}.$
6. :Set $w((A\; \backslash cap\; X,\; B\; \backslash cap\; X))\; =\; c\text{'}(A\text{'},\; B\text{'}).$
7. :Go to step 2.
8. Replace each $\backslash \{v\backslash \}\; \backslash in\; V\_T$ by {{mvar|v}} and each $(\backslash \{u\backslash \},\backslash \{v\backslash \})\; \backslash in\; E\_T$ by {{math|(u, v)}}. Output {{mvar|T}}.

Using the submodular property of the capacity function {{mvar|c}}, 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 {{math|s-t}} cut in {{mvar|G'}} is also a minimum {{math|s-t}} cut in {{mvar|G}} for any {{math|s, t ∈ X}}.

To show that for all $(P,Q)\; \backslash in\; E\_T,$ $w(P,Q)\; =\; \backslash lambda\_\{pq\}$ for some {{math|p ∈ P}}, {{math|q ∈ Q}} throughout the algorithm, one makes use of the following lemma,

: For any {{mvar|i, j, k}} in {{mvar|V_G}}, $\backslash lambda\_\{ik\}\; \backslash ge\; \backslash min(\backslash lambda\_\{ij\},\; \backslash lambda\_\{jk\}).$

The lemma can be used again repeatedly to show that the output {{mvar|T}} satisfies the properties of a Gomory–Hu Tree.

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.

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

| doi = 10.1137/0219009

| last = Gusfield | first = Dan

| title = Very Simple Methods for All Pairs Network Flow Analysis

| journal = SIAM J. Comput.

| volume = 19

| issue = 1

| pages = 143–155

| year = 1990

}}

Andrew V. Goldberg and K. Tsioutsiouliklis implemented the Gomory-Hu algorithm and Gusfield algorithm, and performed an experimental evaluation and comparison.{{cite journal|last=Goldberg|first=A. V.|author2=Tsioutsiouliklis, K.|title=Cut Tree Algorithms: An Experimental Study|journal=Journal of Algorithms|year=2001|volume=38|issue=1|pages=51–83|doi=10.1006/jagm.2000.1136 }}

Cohen et al. report results on two parallel implementations of Gusfield's algorithm using OpenMP and MPI, respectively.{{cite conference

| last1 = Cohen | first1 = Jaime

| last2 = Rodrigues | first2 = Luiz A.

| last3 = Silva | first3 = Fabiano

| last4 = Carmo | first4 = Renato

| last5 = Guedes | first5 = André Luiz Pires

| last6 = Duarte | first6 = Jr., Elias P.

| editor1-last = Xiang | editor1-first = Yang

| editor2-last = Cuzzocrea | editor2-first = Alfredo

| editor3-last = Hobbs | editor3-first = Michael

| editor4-last = Zhou | editor4-first = Wanlei

| contribution = Parallel implementations of Gusfield's cut tree algorithm

| doi = 10.1007/978-3-642-24650-0_22

| pages = 258–269

| publisher = Springer

| series = Lecture Notes in Computer Science

| title = Algorithms and Architectures for Parallel Processing – 11th International Conference, ICA3PP, Melbourne, Australia, October 24–26, 2011, Proceedings, Part I

| volume = 7016

| year = 2011| isbn = 978-3-642-24649-4

}}

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

| last1 = Hartvigsen | first1 = D.

| last2 = Mardon | first2 = R.

| doi = 10.1137/S0895480190177042

| issue = 3

| journal = SIAM J. Discrete Math.

| pages = 403–418

| title = The all-pairs min cut problem and the minimum cycle basis problem on planar graphs

| volume = 7

| year = 1994}}.

• Cut (graph theory)
• Max-flow min-cut theorem
• Maximum flow problem

{{reflist}}

• {{cite book | author = B. H. Korte, Jens Vygen | title = Combinatorial Optimization: Theory and Algorithms (Algorithms and Combinatorics, 21) | url = https://archive.org/details/combinatorialopt00kort_232 | url-access = limited | chapter = 8.6 Gomory–Hu Trees | year = 2008 | publisher = Springer Berlin Heidelberg | isbn = 978-3-540-71844-4 | pages = [https://archive.org/details/combinatorialopt00kort_232/page/n189 180]–186}}

{{DEFAULTSORT:Gomory-Hu tree}}

Category:Combinatorial optimization

Category:Network flow problem

Category:Graph algorithms