Weighted tree representing s-t cuts of a graph
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 maximum flow computations. It is named for Ralph E. Gomory and T. C. Hu.
Definition
Let
be an undirected graph with
being the capacity of the edge
respectively.
- Denote the minimum capacity of an s-t cut by
for each
. - Let
be a tree, and denote the set of edges in an s-t path by
for each
.
Then T is said to be a Gomory–Hu tree of G, if for each ![{\displaystyle s,t\in V_{G}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \lambda _{st}=\min _{e\in P_{st}}c(S_{e},T_{e}),}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
where
are the two connected components of
, and thus
forms an s-t cut in G.
is the capacity of the
cut in G.
Algorithm
Gomory–Hu Algorithm
- Input: A weighted undirected graph
![{\displaystyle G=((V_{G},E_{G}),c)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- Output: A Gomory–Hu Tree
![{\displaystyle T=(V_{T},E_{T}).}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- Set
![{\displaystyle V_{T}=\{V_{G}\},\ E_{T}=\emptyset .}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- Choose some
with |X| ≥ 2 if such X exists. Otherwise, go to step 6. - For each connected component
let ![{\textstyle S_{C}=\bigcup _{v_{T}\in V_{C}}v_{T}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- Let
![{\displaystyle S=\{S_{C}\mid C{\text{ is a connected component in }}T\setminus X\}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- Contract the components to form
where:![{\displaystyle {\begin{aligned}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{aligned}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
is the capacity function, defined as:![{\displaystyle {\begin{aligned}&{\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{aligned}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- Choose two vertices s, t ∈ X and find a minimum s-t cut (A′, B′) in G'.
- Set
![{\displaystyle A={\Biggl (}\bigcup _{S_{C}\in A'\cap S}\!\!\!S_{C}\!{\Biggr )}\cup (A'\cap X),\ }](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle B={\Biggl (}\bigcup _{S_{C}\in B'\cap S}\!\!\!S_{C}\!{\Biggr )}\cup (B'\cap X).}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- Set
![{\displaystyle V_{T}=(V_{T}\setminus X)\cup \{A\cap X,B\cap X\}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- For each
do:- Set
if
otherwise set ![{\displaystyle e'=(B\cap X,Y).}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- Set
![{\displaystyle E_{T}=(E_{T}\setminus \{e\})\cup \{e'\}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- Set
![{\displaystyle w(e')=w(e).}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- Set
![{\displaystyle E_{T}=E_{T}\cup \{(A\cap X,\ B\cap X)\}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- Set
![{\displaystyle w((A\cap X,B\cap X))=c'(A',B').}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- Go to step 2.
- Replace each
by v and each
by (u, v). Output T.
Analysis
Using the submodular property of the capacity function c, one has
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
for some p ∈ P, q ∈ Q throughout the algorithm, one makes use of the following Lemma,
- For any i, j, k in VG,
![{\displaystyle \lambda _{ik}\geq \min(\lambda _{ij},\lambda _{jk}).}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
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
- green circles are vertices of T.
- red and blue circles are the vertices in G'.
- grey vertices are the chosen s and t.
- red and blue coloring represents the s-t cut.
- dashed edges are the s-t cut-set.
- 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.[2]
Andrew V. Goldberg and K. Tsioutsiouliklis implemented the Gomory-Hu algorithm and Gusfield algorithm, and performed an experimental evaluation and comparison.[3]
Cohen et al. report results on two parallel implementations of Gusfield's algorithm using OpenMP and MPI, respectively.[4]
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.[5]
See also
References
- ^ Gomory, R. E.; Hu, T. C. (1961). "Multi-terminal network flows". Journal of the Society for Industrial and Applied Mathematics. 9 (4): 551–570. doi:10.1137/0109047.
- ^ Gusfield, Dan (1990). "Very Simple Methods for All Pairs Network Flow Analysis". SIAM J. Comput. 19 (1): 143–155. doi:10.1137/0219009.
- ^ Goldberg, A. V.; Tsioutsiouliklis, K. (2001). "Cut Tree Algorithms: An Experimental Study". Journal of Algorithms. 38 (1): 51–83. doi:10.1006/jagm.2000.1136.
- ^ Cohen, Jaime; Rodrigues, Luiz A.; Silva, Fabiano; Carmo, Renato; Guedes, André Luiz Pires; Duarte, Jr., Elias P. (2011). "Parallel implementations of Gusfield's cut tree algorithm". In Xiang, Yang; Cuzzocrea, Alfredo; Hobbs, Michael; Zhou, Wanlei (eds.). Algorithms and Architectures for Parallel Processing – 11th International Conference, ICA3PP, Melbourne, Australia, October 24–26, 2011, Proceedings, Part I. Lecture Notes in Computer Science. Vol. 7016. Springer. pp. 258–269. doi:10.1007/978-3-642-24650-0_22.
{{cite conference}}
: CS1 maint: multiple names: authors list (link) - ^ Hartvigsen, D.; Mardon, R. (1994). "The all-pairs min cut problem and the minimum cycle basis problem on planar graphs". SIAM J. Discrete Math. 7 (3): 403–418. doi:10.1137/S0895480190177042..
- 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.