数理解析研究所講究録
第 833 巻 1993 年 120-130120

A Faster Algorithm
for the Minimum Capacity Cut Problemof Undirected Networks
Tadashi ONO(小野Toshihide IBARAKI

Hiroshi NAGAMOCHI

(永持

正)

(茨木 俊秀)仁)

Department of Applied Mathematics and Physics,
Faculty of Engineering,
Kyoto University

1

Introduction

Let $\mathcal{N}=(G=(V, E),$ ) be a simple undirected network with a set of vertices and a set(the set of nonnegative reals) gives the capacities of edges. Theof edges, whereminimum capacity cut problem is to find a nonempty subset $U\subset V,$ $U\neq V$ that minimizes
the total capacity of the edges between and $V-U$ .
Gomory and Hu [3] show that the optimal solution of this problem can be obtainedby solving $|V|-1$ max-flow problems. The currently best bound for solving the max-flow
problem is $O(mn\log(n^{2}/m))$ due to Goldberg and Tarjan [2], where $n=|V|$ and $m=|E|$ .
Thus the time complexity of Gomory and Hu’s method is.
Padberg and Rinaldi [8] present an improved approach such that two vertices are shrunk
into a single vertex to obtain a smaller network after examining the minimum capacity cut
separating these vertices. Although their method requires $n-1$ max-flow computations in
the worst case as Gomory and Hu’s does, they also provide a simple test to shrink a pairof vertices, by which the number of max-flow computations which need to be conducted
is considerably reduced. Their algorithm is considered to be one of the fastest one in thepractical sense.
$V$

$c$

$c:Earrow \mathcal{R}^{+}$$U$$O(mn^{2}\log(n^{2}/\gamma\gamma l))$

$E$

121
In this paper, we present an efficient implementation of a faster $O(mn+n^{2}\log n)$ algorithm
proposed by Nagamochi and Ibaraki [6], and add various mechanisms so that as many edges
as possible can be shrunk in each iteration. From numerical experiments, we find out that
our implementation is much faster and more stable t,han Padberg and Rinaldi’s for a wide
variety of networks.

2

Preliminaries

Let $\mathcal{N}=(G=(V, E),$ ) stand for a simple undirected network with a vertex set , an edge
set $E$ , and nonnegative real capacities $c(e),$ $e\in E$ . We denote $e=(u, v)$ if the end verticesof $e\in E$ are and . A nonempty subset $U\subset V,$ $U\neq V$ is called a cut, and the capacity
is given by $c(U)= \sum_{u\in U,v\in \mathcal{V}-U}c(u, v)$ . For notational convenience, a singleton set
for a cut
$V$

$c$

$u$

$v$

$U$

may also be written as . The minimum capacity cut problem is the problem of findingthat minimizes $c(U)$ in . We simply call sucha minimum cut and denote by
a cut
the capacity of a minimum cut of .
For $y\in V$ , the capacity of a cut with the minimum capacity among the cuts that.
separate and is denoted
is defined as follows: merge and into a single vertex
Shrinking edge $e=(u, v)$ of
by deleting edge $e=(u, v)$ , and combine the resulting multiple edges with the same pair ofend vertices into a single edge having the sum of the capacities of such edges. We denote theinstead of $G/e$ ),network obtained by shrinking as $\mathcal{N}‘=(G/e, c’)$ (we may write $G/\{u,$where is the capacities of the resulting network.
$\{u\}$

$u$

$U$

$U$

$\mathcal{N}$$\mathcal{N}$$\lambda(\mathcal{N})$

$x,$
$x$

$y$

$\lambda(x, y)$$\mathcal{N}$

$u$

$v$

$v\}$

$e$

$c’$

3

Shrinking Edges by CAPFOREST

3.1

Computing the Minimum Cut Based on Shrinking

In this section, we describe a general framework to compute$\lambda(\mathcal{N})$by using edge shrinking.

LEMMA 1 For a network $\mathcal{N}=(G, c)$ and a shrunk network $’=(G/e, c’)$ where $e=(x, y)\in$, we have$E$$\lambda(\mathcal{N})=\min\{\lambda(\mathcal{N}’), \lambda(x, y)\}$LEMMA 2 Let$\overline{\lambda}$.

(1)$\square$be the capacity of a cut $X\subset V$ . If there exist two vertices

$x$

and

$y$

satisfying

122$\lambda(x, y)\geq\overline{\lambda}$(2),

then there are no cuts separating
PROOF.

$x$

and

$y$

whose capacities are less than

It is immediate from the definition of$\lambda(x, y)$.

$\overline{\lambda}$.

$\square$for network
obtained
If condition (2) holds for and , we haveby shrinking and . For an edge $e=(x, y)$ which satisfies the condition (2) for a , we callsuch an edge shrinkable.
in the following manner: we first
Based on this observation, we can compute
examine all $c(v),$ $v\in V$ in the given network, and store the smallest $c(v)$ as A. Second,$x$$\mathcal{N}’$$\lambda(\mathcal{N})=\min\{\lambda(\mathcal{N}’),\overline{\lambda}\}$$y$$\overline{\lambda}$

$x$

$y$

$\lambda(\mathcal{N})$find two vertices and satisfying (2) for the current , and shrink and into a vertex. When we repeat this shrinking until the number of vertices‘, setting.
becomes two, the current is equal toThis procedure is stated as follows.
$\overline{\lambda}$

$x$

$x$

$y$

$y$

$\overline{\lambda}=\min\{\overline{\lambda}, c’(x’)\}$$x$$\overline{\lambda}$$\lambda(\mathcal{N})$Procedure SHRINK
Input: a simple undirected network $\mathcal{N}=(G, c)$
Output:begin$\lambda(N)$$\overline{\lambda}$$:= \min\{c(\iota))|v\in V\};\mathcal{N}’$$:=(G’=(V’, E’),$

$c’$

)

$:=\mathcal{N}$;while $|V’|\geq 3$ do
begin
is found then $:=c’(X)$ ;if a cut $X\subset V$ with c’(X);such thatFind two vertices
Shrink and into and let $\mathcal{N}’=(G’=(V’, E’),$ ) be the resulting network;;
end;
Conclude thatend.
$<\overline{\lambda}$$\lambda(x,y)\geq\overline{\lambda}$$x,$ $y$$x$$\overline{\lambda}$$y$$\overline{\lambda}$

$x’$

$c’$

$:= \min\{c’(x’),\overline{\lambda}\}$$\lambda(\mathcal{N})=\overline{\lambda}$

We can get the minimum cut capacity after performing $n-1$ operations of vertex shrink, we may computebying. In order to find two vertices and such that, the above condition
the max-flow algorithm. In this case, after setting A
is satisfied. Padberg and Rinaldi) algorithm [8] is the first one which is based on procedure
A using a simple
SHRINK. Specifically, they try to find an edge $e=(x, y)$ withtest, and rely on a max-flow algorithm only when this heuristic test fails to find such edge
$x$

$y$

$\lambda(x, y)$$\lambda(x, y)\geq\overline{\lambda}$$:= \min\{\overline{\lambda}, \lambda(x, y)\}$$s$$\lambda(x, y)\geq$$e=(x, y)$ (see [8], for detail).

123
Algorithm CAPFOREST

3.2

Algorithm CAPFOREST presented by Nagamochi and Ibaraki [6] computes the following
lower bound $q(e)$ on
for all edges $e=(x,y)$ in $O(m+n\log n)$ time.
$\lambda(x, y)$

LEMMA 3 [6] The $q(e)$ obtained by CAPFOREST satisfies$\lambda(x, y)\geq q(e)$,$e=(x, y)\in E$ ,(3)

and at least one edge $e^{*}=(x^{*}, y^{*})\in E$ satisfies$q(e^{*})=\lambda(x^{*}, y^{*})$.

(4)$\square$

To computebased on procedure SHRINK, we exploit these $q(e)$ obtained by CAPFOREST for finding shrinkable edges.
$\lambda(\mathcal{N})$LEMMA 4 Let $q(e)$ be the lower bound obtained by CAPFOREST, anda cut which has already been detected. If$q(e)\geq\overline{\lambda}$

then

$e$

,

$\overline{\lambda}$

be the capacity of(5)is shrinkable.

PROOF.

It is obvious from Lemma 2 and condition (3).

$\square$By employing CAPFOREST to find shrinkable edges in algorithm SHRINK, we have the, which is a modification of the original algorithm byfollowing algorithm to compute
Nagamochi and Ibaraki [6].
$\lambda(\mathcal{N})$Algorithm CF-SHRINK
Input: a simple undirected network $\mathcal{N}=(G=(V, E)_{7}c)$
Output:$\lambda(\mathcal{N})$begin

X $:= \min\{c(v)|v\in V\}\cdot,$$\mathcal{N}’$$:=(G’=(V’, E’),$

while $|V’|\geq 3$ do
begin
Execute CAPFOREST $(G’, c’;q)$ ;for the edge
while there exist edges $e=(x, y)$ with$\overline{\lambda}$$:= \min\{\overline{\lambda}, \lambda(x^{*}, y^{*})\}$

$c’$

)

$(x^{*}, y^{*})$$:=\mathcal{N}$;of (4);do$q(e)\geq\overline{\lambda}$

124
begin
Shrink$x,$ $y$

into

$x$

$:= \min\{c(x’),\overline{\lambda}\}$$\overline{\lambda}$

and let‘$\Lambda^{r/}=$$(G’= (V‘, E’),$$c’$) be the resulting network;

;

end
end
Conclude thatend.

$\lambda(\mathcal{N})=\overline{\lambda}$;

Once we execute CAPFOREST in CF-SHRINK, we can find at least one edge $e^{*}=$is shrinkable after settingthat satisfies (3) by Lemma 3, which implies that
. Therefore, we can continue vertex shrinking until the number ofA
can be computed by executing CAPFOREST at mostvertices becomes two. Hence,$n-2$ times, and thus the running time of CF SHRINK is $O(mn+n^{2}\log n)$ .
$(x^{*}, y^{*})$$(x^{*}, y^{*})$$:= \min\{\overline{\lambda}, \lambda(x^{*}, y^{*})\}$$\lambda(\mathcal{N})$3.3

Algorithm MODIFIED CAPFOREST

In this section, We revise CAPFOREST in order to find shrinkable edges and small cuts
more efficiently. The revised CAPFOREST, called MODIFIED-CAPFOREST, computes a
setof shrinkable edges and detects a certain cut capacity in addition to the originalcomputation of CAPFOREST.
$T$

$a$

Algorithm MODIFIED-CAPFOREST
Input: a simple undirected network $\mathcal{N}=(G=(V, E),$ ), and the currently obtained$(G, c,\overline{\lambda};q, T, \alpha)$$c$;minimum cut capacity
Output: the lower bound $q(e)$ , a shrinkable edge set , and a certain cut capacity
begin
Label all vertices $v\in V$ and all edges $e\in E$ unscanned;$r(v)$ $:=0,$ $a(v):=0$ , for all $v\in V$ ;$q(e)$ $:=0$ , for all $e\in E$ ;$\overline{\lambda}>0$

$T$

$T$

$:=\emptyset;\alpha’$$:=0,\cdot$

while there exist “unscanned” vertices do
begin
Choose an (unscanned’ vertex with the largest ;;Of $:=\alpha’+c(x)-2r(x);\alpha(x)$for each vertex adjacent to by an (unscanned’ edge do$x$$:=\alpha’$

$y$

$x$

$r$

$\alpha$

;

125
begin
if $r(y)<\overline{\lambda}\leq r(y)+c(e)$ then $T:=T\cup\{e\}$ ;$q(e)$ $:=r(y)+c(e);r(y)$ $:=r(y)+c(e)$ ;Mark “scanned” ;endMark “scanned”;
end$:= \min\{\alpha(v)|v\in V\}$ ;
$e$

$x$

$\alpha$end.
The output $q(e)$ is the same as by CAPFOREST [6], so it also satisfies conditions (3)and (4).
THEOREM 5 Let
define a subgraph ofsuch asedge set obtained by MODIFIED-CAPFOREST is a maximal spanning forest of$G$$G_{q,\overline{\lambda}}$$G_{q,\overline{\lambda}}=(V, \{e\in E|q(e)\geq\overline{\lambda}\})$$T$

PROOF.

See [7].

. An$G_{q,\overline{\lambda}}$.

$\square$

The network resulting from shrinking all edges in a maximal spanning forest ofisthe same as the one obtained by shrinking all edges in. The mechanism of identifying$T$$G_{q,\overline{\lambda}}$$G_{q,\overline{\lambda}}$such in MODIFIED-CAPFOREST saves the unnegligible time, if compared with the time
to collect all edges inof in from scratch.
Next we mention about the capacity of a certain cut.
$T$

$G_{q,\overline{\backslash }}$$T$$\alpha$LEMMA 6 Let $x_{i}(1\leq i\leq n-1)$ be the i-th vertex visited by MODIFIED-CAPFOREST

and define $X_{i}=\{x_{1)}x_{2}, \ldots, x_{i}\}$ . Then $Cy(X;)=c(X_{i})$ .

$\square$By Lemma 6, the minimum capacity $0=\min_{i}\alpha(x_{i})$ among the cuts
may be relatively
small, because CAPFOREST tends to select a subset of some vertices connected each otherby those edges with relatively large capacities in the early stage of computation. If this a, we update A $:=a$ . So A may decrease in an earlier stage, thereby enlarging
satisfies
the set of edges satisfying condition (5).
By replacing CAPFOREST with $MODIFIED_{-}CAPFORES^{r}l^{\urcorner}$ in CF-SHRINK, we havethe following more efficient algorithm.
$X_{i}$$\alpha<\overline{\lambda}$

Algorithm MCF
Input: a simple undirected network $\mathcal{N}=(G=(V, E),$ )
$c$

126
Output:begin$\overline{\lambda}$$\lambda(\mathcal{N})$$:= \min\{c(v)|v\in V\};N’$ $:=(G’=(V’, E’),$ $c’$ )while $|V$ ‘
begin$|\geq 3$

do

Execute MODIFIED-CAPFOREST$\overline{\lambda}$$:= \min\{\alpha,\overline{\lambda}\}$$(G‘, c’,\overline{\lambda};q, T, \alpha)$;;

for $e=(x, y)\in T$ do
begin
into
Shrink$x,$ $y$$\overline{\lambda}$$:=\mathcal{N},\cdot$

and let $\mathcal{N}’=(G’=(V’, E’),$ ) be the resulting network;$x’$$:= \min\{c(x’),\overline{\lambda}\}$

$c’$

;

end
end

Conclude thatend.

4$\lambda(\mathcal{N})=\overline{\lambda}$;

Computational Experiments

In this section, we report the results from the computational experiments conducted to evaluate the performance of the proposed algorithm MCF. All computer programs were coded in
FORTRAN 77 in double precision and run on a workstation SUN SPARC 1 IPX.

4.1

Generation of Networks for Experiments

In our numerical experiments, we specify network types by the following four parameters:

the number of vertices , the density of edges $d= \frac{2m}{n(n-1)}\cross 100$ (%) (
$n$

$m$

is the number ofedges), a decomposition number $k(1\leq k\leq n)$ , and a constant satisfying $0<p\leq 1$ (for$k\geq 2)$ . Based on these parameters, we generate a network as follows: First, we construct a$p$connected graph with$n$vertices and $\frac{n(n-1)(d/100)}{2}$ edges by randomly generating an edge

between a pair of vertices, after creating a Hamilton path to ensure the connectivity. Second,
we define the capacity of each edge by the following rule. When $k=1$ , capacity of each edge
is randomly chosen from the interval $[0,100$ ) uniformly. When $k\geq 2$ , we divide vertices into
subsets randomly (each subset is called a cluster), and the capacities of the edges connecting
two vertices in the same cluster are selected from $[0,100$ ), while the capacities of the rest
$k$

127
of edges are randomly chosen from $[0,100p$ ). In our experiments, is set to $1/n$ except inFigure 6 so that a set of clusters is likely to form a minimum cut in the generated network.
Note that $p=1/n$ is used because the ratio of the capacity $c(x)$ of a singleton
to that of$p$$\{x\}$

non-singleton set is at most

4.2$\frac{n-1}{n(n-1)/2}=\frac{2}{n}$.

Computational Results

By solving the networks generated in the above manner, we compare the average runningtimes of Padberg and Rinaldi’s algorithm (abbreviated to PR), the proposed algorithm (abbreviated to MCF), and a single max-flow computation by Goldberg and Tarjan [2] (abbreviated to MAXFLOW), where ten instances are tested with the same four parameter values.
Figures 1 and 2 show the CPU time of the above three algorithms for various values offor density $d=50$ (%), for $k=1$ and $k=2$ respectively. From these figures, we can seethat MCF is much faster than PR, and the larger the number of vertices is, the greater thedifference of the computational time becomes. When $k=2$ , PR takes longer time comparedwith case of $k=1$ , because the network loses uniformity of capacity distribution and it
becomes hard to find shrinkable edges only by heuristic test. Contrary to this, MCF could
accelerate the shrinking process, with the help of the value of a small capacity cut. As aresult, the difference between MCF and PR becomes greater when is changed from 1 to 2.
Figures 3 and 4 illustrate the CPU time of the above algorithms for different densities.
In Figure 3, running time of PR fluctuates depending on the density. In PR, the probabilityof finding shrinkable edges tends to become small when the density is low, and hence thenumber of times to rely on max-flows computations increases. Conversely, when density ishigh, the probability that the heuristic test of PR for a single edge succeeds becomes very
close to 1. The time required to find one shrinkable edge by PR is shorter than that by
MCF. For this reason, PR is slightly faster than MCF if $d=100$ (%) and $k=1$ (Figure 3).
However, for $k=2$ (Figure 4), computing helps MCF run faster even for highly dense
networks.
Figure 5 shows the results when the decomposition number changes. As we discussed
above for case of $k=2$ previously, an edge whose both end vertices are in the same cluster
is not likely to be shrinkable by the heuristic test in PR. It still has the same difficulty for$3\leq k\leq 20$ . When $k\geq 50$ , the capacities distribute nearly uniformly in the sense that a
handful of edges with relatively large capacities are scattered over the ntire network, andsuch edges can be shrunk in an early stage of the algorithm, resulting in the high performance$n$$\alpha$

$k$

($y$

$k$

$e$

128
of PR. On the contrary, MCF is litt,le influenced by the decomposition number
remains faster than PR.

$k$and always

Figure 6 shows the effect of parameter in the $rallge$ [0.0005, 1]. Note that when $p=1$ ,there is one cluster. When $p=0.005=2/n$ , since the expectation of the capacity of asingleton is approximately equal to that of one clust,er produced by $k=2$ , both a singleton
and non-singleton cuts may be a minimum cut. Generally by the heuristic test in PR, it
is difficult to find a minimum cut if the capacities of both types of cuts are nearly equal.
Therefore PR takes large time for $0.005\leq p\leq 0.1$ .
From the above observation, we conclude th\^ot proposed MCF is much faster than PR.
MCF may be considered as one of the fastest practical program available for the minimum
capacity cut problem. Its running time is almost comparable (i.e., always at most $O(mn+$$n^{2}\log n)$ times) with the fastest max-flow algorithm. Another advantage of MCF is its simplicity of implementation, because MCF basically consists only of MODIFIED-CAPFOREST,
while PR requires the max-flow algorithm and a sophisticat $ed$ control for computing heuristic
tests. Only in the case of $k=1$ and $d\geq 95$ (%), PR runs slightly faster than MCF in above$p$

experiment.

4.3

A Hybrid Implementation: Algorithm HCF

In order to improve our algorithm MCF for the case of $k=1$ and $d=100$ (%), we also propose
algorithm HCF, a hybrid version of MCF and PR obtained by including the heuristic test of

PR into MCF. The reason why PR runs faster than MCF in case of $k=1$ and $d\geq 95$ (%)
is that the heuristic test for shrinking succeeds with probability nearly close to 1. Only inthis situation, the time required by PR for finding one shrinkable edge is shorter than MCF.
We want to capture this power of the heuristic test, but have to take care not to increase therunning time of MCF for other cases. Concretely speaking, after MODIFIED-CAPFOREST
followed by shrinking , we execute the heuristic test only for those edges having relatively
large capacities among the edges incident to the vertex that was shrunk most recently. We
continue this test only when the previous one successfully finds a shrinkable edge, and once
it fails, we go back to start MODIFIED.-CAPFOREST (see [7], for detail).
As aimed, the above heuristics works effectively for the case of $k=1$ and $d\geq 95$ (%) in
HCF. As a result, HCF runs faster than any of PR and MCF, as shown in Figure 3. It is also
observed that HCF performs almost the same as MCF in other cases. The HCF algorithm isslightly complicated than MCF to implement.
$T$

129
5

Conclusion

By revising some part of the algorithm proposed by Nagamochi and Ibaraki [6], we obtained
a practically efficient implementation for computing thecapacity cut of undirected
networks. From computational results, we have shown that MCF is faster than PR proposed
by Padberg and Rinaldi in most cases except the case in which capacities are uniformly$\min i\iota n\iota lnl$

distributed on network with very high density. Moreover, an important advantage of MCF
is in its simplicity of implementation. We also proposed a hybrid implementation obtainedby including the heuristic test of PR into MCF, and sh wed that it is never slower than anyof the PR and MCF for all types of networks we examined in this study.
$0$

References[1] L. Ford, and D. Fulkerson: “Maximal Flow Through a Network,“ C’anadian Journal of
Mathematics, Vol. 8, pp.399-404, 1956.
[2] A. Goldberg and T. Tarjan: “A new approach to the maximum flow problems,” Pro-

ceedings of 18th A CM Symposium on the Theory of Co mputing, pp.136-146, 1986.
[3] R. Gomory and T. Hu: “Multi-terminal network flows,“ ’9lAM Journal on Applied Mathematics, Vol. 9, pp.551-570, 1961.

[4] T. Ibaraki: Algorithms and Data Structu$7^{\cdot}es$(in Japanese), Shokodo, 1989.

[5] T. Ibaraki and M. Fukushima: FORTRAN 77 optimization Programming (in Japanese),
Iwanami-Shoten, 1991.
[6] H. Nagamochi and T. Ibaraki: “Computing edge-connect,ivity in multigraphs and capacitated graphs,” SlAM Journal on Discrete Mathematics, Vol. 5, pp.54-66, 1992.

[7] T. Ono: “A Faster Algorithm for the Minimum Capacity Cut Problem of Undirected
Networks,” Master thesis, Department of Applied Mathematics and Physics, Faculty ofEngineering Kyoto University, 1993.
[8] M. Padberg and G. Rinaldi: “An efficient algorithm for the minimum capacity cut
problem,” Mathematical Programming, Vol. 47, pp.19-36, 1990.

130$\wedge\vee\dot{8}$$\wedge\vee\dot{8}\omega$svE$\xi v$$6\supset$$\cup\alpha\supset$

Figure 1:

CPU time of algorithm PR, MCF and
MAXFLOW when the number of vertices cbanges$\iota$(d=50(%), k $=1,$ p $=1/n$ ).

\S .

svE
.

$\cup\supset a$

Figure 2: CPU time of algorithm PR, MCF and
MAXFLOW when the number of vertices n changes(d=50(%), k $=2,$ p $=1/n$ ).

$\vee\wedge 8n$

gv$b\supset$

Figure 3: CPU time of algorithm PR, MCF, HCF
and MAXFLOW when the edge density d Changes(n $=400,$k $=1,$p $=1/n)$ .

of algorithm PR, MCF
Figure 4: Cl)Uand MAXFLOW whenedge density d changes(n $=400,$k $=2, l)=|/n)$ .
$\uparrow\dot{|}l11$)$t1_{h}e$$\vee\wedge\dot{o}\Re$$a\in v$$\circ\supset\alpha$

Figure 5: Cl) time of $algorit1_{h}m$ PR, MCF andM A XFLOW for various decomposition number$\cup$$k$$(?l=400,$d $=50(()),$ l $=1/?1$ ).

$\wedge\vee\dot{8}a$$5\in\Phi$$\circ\supset$

Figure 6: CPU time of algorithm PR, MCF and400, dMAXFLOW for various
50(%), k $=2$ ).
$\mathfrak{c}0l1\backslash ta11\uparrow p(\uparrow\iota=$$=$