Computing All Small Cuts in an Undirected Network.
Let $\lambda({\cal N})$ denote the weight of a minimum cut in an edge-weighted undirected network ${\cal N}$, and  $n$ and $m$ denote the numbers of vertices and edges, respectively. It is known that $O(n^{2k})$ is an upper bound on the number of cuts with weights less than $k\lambda({\cal N})$, where $k\geq 1$ is a given constant. This paper first shows that  all cuts of weights less than $k\lambda({\cal N})$ can be enumerated in $O(m^2n+n^{2k}m)$ time without using the maximum flow algorithm. The paper then proves for $k<\four$ that $n\choose 2$ is a tight upper bound on the number of cuts of weights less than $k\lambda({\cal N})$, and that all those cuts can be enumerated in $O(m^2n+mn^2\log n)$ time.
Introduction
Let N stand for an undirected network with its edges being weighted by non-negative
real numbers. Counting the number of cuts with small weights, and
deriving upper and lower bounds on their numbers play an important role in
the reliability analysis of probabilistic networks whose edges are subject to
failure [2], the graph augmentation problem, i.e., the problem of increasing
the edge-connectivity by adding the smallest number of edges to a graph
[15], and other problems.
Let -(N ) denote the weight of a minimum cut in N , and let n and m be
the numbers of vertices and edges, respectively. It is known that an upper
bound on the number of minimum cuts is
n(n 1), which is achievable
when N is a ring consisting of n edges with weight -(N )=2 [1, 3].
Recently, Vazirani and Yannakakis [17] showed that cuts of weights no
more than the r-th minimum weight can be enumerated by O(rn) maximum
ow computations. Based on a probabilistic analysis, on the other hand,
Karger [10] derived for arbitrary k  1 an upper bound O(n 2k ) on the
number of cuts of weights no more than k-(N ).
In this paper, for arbitrary k > 1, we enumerate all cuts with weights
no more than k-(N ) without relying on the maximum
ow algorithm. Our
enumeration algorithm makes use of the edge splitting operation (see Section
to reduce the number of vertices by one while preserving the edge-
connectivity. We repeatedly apply the edge splitting operation until the net-work
has only two vertices, and obtain a sequence of such networks N i with
2. After enumerating all small cuts (of weights no
more than k-(N)) in N 2 , the set of small cuts in N i+1 are then computed
from the set of those cuts in N i in the order of
can show that the entire running time of this algorithm is O(m
Thus, if there are (n 2k ) such cuts, each cut is found in linear time. We
then prove that the number of cuts with weights less than 4-(N ) is at most
(i.e., the upper bound on the number of minimum cuts), that this bound
is tight for any number n of vertices, and that 4is best possible for
to
be an upper bound. The time of our algorithm to enumerate all the cuts
with weights less than 4-(N ) becomes O(m 2 n +mn 2 log n).
Very recently, Henzinger and Williamson [9] extended the above argument
to prove an O(n 2 ) upper bound on the number of cuts with weights
less than2
The remainder of this paper is organized as follows. Section 2 describes
basic denitions and notations. Before presenting an algorithm to compute
all small cuts, we review in Sections 3 - 5 the concepts of s-connectivity,
weighted edge-splitting, and vertex isolation, and discuss how to compute
them. Based on these, Section 6 gives the algorithm to compute all small
cuts. Finally, Section 7 derives an upper bound on the number of small
cuts with weights less than 4-(N ), and applies this to evaluate the time
complexity of the above algorithm.
Preliminaries
c) be an undirected network with a set V of vertices and a
set E of edges weighted by c
,
is the set of non-negative
real numbers. Throughout the paper, we assume, for notational convenience,
that (V; E) forms a simple complete graph, and denote by E c  E the set
of edges with positive weights (from the computational point of view, we
only have to maintain graph (V; E c )). An edge e with its end vertices u
and v is denoted by (u; v) or (v; u), and its weight c((u; v)) (= c((v; u))) is
written by c(u; v) (= c(v; u)), unless confusion arises. A vertex adjacent to
a vertex by an edge with positive weight is called a neighbor of v. Let
denote the set of neighbors of a vertex
v.
A singleton set fxg may be simply written as x, and \  " implies proper
inclusion while \  " means \  " or
For two disjoint subsets X;Y  V of a network N , E(X;Y
the set of edges, one of whose end vertices is in X and the other is in Y , and
denotes the sum of edge weights in E(X;Y ; N ). E(X;Y
and c(X; Y ; N ) may be written as E(X; Y ) and c(X; Y ), respectively, if N
is clear from context.
A cut is dened as a subset X of V with We say that a cut
separates two disjoint subsets Y and Y 0
of
(or Y  V X and Y 0  X) hold. The weight of a cut X is dened by
which may be written as c (X; N ) or c (X). A cut is called
an -cut if it has weight . Clearly, a cut X and its complement V X
(which is also a cut) have the same weight c X). For this
reason, we often do not distinguish two cuts X and V 0 X. In particular,
in generating small cuts, we want to generate only one of X and V 0 X.
;. For two crossing cuts X; Y , we can easily see the following
identity (see Fig. 1).
The local edge-connectivity (x;
to be the minimum weight of a cut that separates x and y (we dene
is a minimum cut if c (X;N ) is minimum
among all cuts in N . The weight of a minimum cut is called the
global edge-connectivity of N and denoted by (N ) (we dene (N
if In other words, (N g. Throughout
this paper, we assume (N
Computing s-Connectivity  s (N )
For a network N , choose a vertex s as a designated vertex. A cut X is called
that  denotes proper inclusion). The
is the weight of a minimum s-proper cut (we dene
In other words,
called
if c(X; N
Lemma 3.1 For a network c) with a designated vertex
the s-connectivity  s (N ) and an s-tight cut T can be computed in O(n(m+
log n)) time.
Proof. Assume n  3. We use the O(m
algorithm [13] that visits every vertex exactly once in the following max-
adjacency order: (i) It rst visits s, and (ii) it chooses the i-th vertex v i
from the unvisited vertices so that c(fv 1
are the vertices visited so far. It is known [13]
that the resulting order
of vertices satises
(only positive capacities are handled in [13], but (3.2) follows from [13] by
allowing capacities to take zero. See [6, 7, 14, 16] for simpler proofs of this
property). Clearly, s 6= v n01 ; v n . Let N n := N and N n01 be the network
obtained from N by contracting v n01 and v n into a single vertex. Any cut
that separates v n01 and v n is s-proper, and hence the minimum weight of
such a cut is c(v n ; N n ) by (3.2). Any s-proper cut that does not separates
v n01 and v n remains in the contracted network N n01 . Thus, we have
Therefore, by repeating this traversal and contraction procedure until the
network has three vertices, - s (N ) is equal to
i is the last vertex in N i in the above traversal procedure. An s-tight
cut in N can be obtained as the set of vertices in V that are contracted into
the vertex v 0
Weighted Edge-Splitting
Edge splitting is one of the most useful operations, which reduces the size of
a graph while preserving edge-connectivity [4, 5, 11, 12]. This section denes
the operation of weighted edge-splitting and derives some key lemmas.
Given a network a designated vertex s 2 V , vertices
(possibly non-negative real    max , where
we construct the following network
(in case of
We say that N 0 is obtained from N by edge splitting (s; u)
and (s; v) of weight , and denote the resulting network N 0 by N =(u; v; ).
Fig. 2. Clearly, for any cut X,
separates fsg and fu; vg
and hence  s (N =(u; v; holds for any    max . Let  s (u; v; N )
denote the maximum  such that    max and  s (N =(u; v;
i.e.,
Any s-tight cut in N remains s-tight in network N =(u; v; ") for
Lemma 4.1 For a network c) with a designated s 2 V and two
distinct
denote the network N =(u; v; )
with
can be computed in O(n(m
)), then N 0
has
an s-tight cut T such that fu; vg  T . Furthermore, such T can be
found in O(n(m
Proof. We show that  s (u; v; N ) can be determined by computing how
much N loses the s-connectivity by the edge splitting (s; u) and (s; v) of
weight  v)g. Let N
we see from (4.1) that any s-tight cut T in N max separates s and fu; vg.
. Therefore, from
(4.2), we have
By Lemma 3.1,  s (N and an s-tight cut T in N max can be
determined in O(n(m log n)) time, respectively. This proves (i).
hold in N 0
. Also the above cut T in N max
hence it is also s-tight in
, proving (ii). 2
Call a weighted edge splitting of (s; u) and (s; v) by  to be safe if  -
s (u; v; N ). Notice that (u; u; c(s; u)=2) is a safe edge-splitting if jNB(s;N
1, because any s-proper cut X that separates s and u satises c(X; N
c( ~
is an s-proper
cut. We will show in the next section that safe weighted edge-splittings
at s can be repeated for various u and v in NB(s;N ), until the resulting
network N 0 has no neighbor of s (i.e., all edges (s; u),
We say that such N 0 is obtained by isolating s from N . It is
known in [4] that such N 0 always exists.
However, it is not trivial to show that any designated vertex s can be
isolated after nite number of safe weighted edge-splittings. Frank [4] rst
proved that any vertex s can be isolated by repeating safe weighted edge-
splittings at s at most O(n) times. On the other hand, the new algorithm
proposed in the next section executes safe weighted edge-splittings at most
jNB(s;N )j times, not just O(jV times (this fact will be crucial to the time
complexity of our nal algorithm for enumerating small cuts in Section 6).
The next two lemmas describe some properties of the network obtained
by isolating s, and s-tight cuts, which will be used to validate the new
algorithm in the next section.
Lemma 4.2 For a network c) with a designated vertex
be the network obtained from N by isolating s, and let N s
be the network obtained from N 0
by eliminating s. Then:
(a) For every nonempty X  V s, c(X; N s
Proof. Immediate from the denition. 2
Lemma 4.3 For a network c) with a designated vertex
the following properties hold.
any s-tight cut T in N .
(ii) For two
and T be two s-tight cuts in N such
that fu; vg \ T
holds.
Proof. (i) Assume that an s-tight cut T satises NB(s;N
is also an s-proper
cut. Clearly,
by NB(s; N ) Therefore, we have c(T ) > c(R), contradicting the
s-tightness of c(T ).
(ii) Assume that T 0 [fvg 6 T , i.e., T 0 T 6= ;. We see that two cuts T 0
and
T cross each other, since
are s-proper. Since (s; u) 2
E(T positive weight, c(T
From (2.1), however
is a contradiction. 2
5 Algorithm to Isolate Vertex s
Based on the properties discussed so far, we will show that the next algorithm
isolates s by repeating weighted edge-splitting at s O(n) times.
Procedure ISOLATE
Input: a network c) and a designated vertex
Output: a network N
and a set Q s of triplets (u; v; )
that are used to isolate s;
3 while jNB(s;N
do
:= fug for a u 2 NB(s; N
6 Choose a u 2 NB(s; N
and a v 2 NB(s;N
7 Compute
11 Find an s-tight cut T with fu; vg  T in N
14 end;
3 := N
for the u 2 NB(s;N 3 )
s be the Nfrom which s is removed
19 end.
Theorem 5.1 Algorithm ISOLATE correctly isolates s 2 V of a network
after repeating edge-splitting at most jNB(s;N )j times, and
runs in O(jNB(s;N )jn(m
Moreover, the resulting network N s has no more edges with positive weights
than N .
Proof. To prove the correctness of ISOLATE, we rst note that lines 5, 6
and 11 of ISOLATE are always possible to perform (clearly any other lines
can be carried out). Since jNB(s;N)j  2 holds in the while loop, we can
choose a u 2 NB(s;N ) in line 5. During the while loop, T 3
is set to be either
a single vertex u 2 NB(s;N 3 ) or an s-tight cut T in the current network
0 . If T 3 is a single vertex, line 6 can be clearly performed. Furthermore,
Lemma 4.3(i) guarantees that line 6 can be performed if T 3 is an s-tight cut
in N
3 . As to the s-tight cut T in line 11, Lemma 4.1(ii) guarantees that it
always exists and can be found in O(n(m
Next we show that the while loop terminates after a nite number of
iterations. For this, we prove that jNB(s;N
j decreases at least by 1
after each execution of the while loop, which implies that the while loop of
lines 3 - 14 is repeated at most jNB(s;N )j 1 times (until jNB(s;N
holds). First note that jNB(s; N
decreases by 1 if line 5 is executed.
line 10 holds, we see that the s-tight cut T in line 11 contains the previous
applies if T 3 is s-tight
in the current network, and T consists of a single
vertex u. Thus, jNB(s;N
decreases at least by 1. If line 10 does
not hold, jNB(s;N
3 )j again decreases at least by 1 since one of u and v
is no longer a neighbour of s, while T 3 remains unchanged. Therefore,
j decreases at least by 1 after each execution of the while
loop. This proves the correctness.
As shown in the above, the while loop is repeated at most n time. Since
lines 7 and 11 can be carried out in O(n(m
(i) and (ii), respectively, and the time for other lines in the while loop is
minor, the entire running time is O(n(m
Finally note that jNB(s;N )j edges with positive weights incident to s are
removed in the resulting network N s . Furthermore, since at most jNB(s;N )j
edge-splittings, including the one in line 16, are applied in ISOLATE, at
most jNB(s;N )j 1 new edges with positive weights are created in N s
This shows the last statement of the lemma. 2
Recently, Gabow [8] developed an O(n 2 m log(n 2
for isolating a vertex s, independently of us. Our algorithm ISOLATE
repeats a modication of the O(mn
of [13] O(n) times, while Gabow's algorithm applies Hao and Orlin's
O(nm log(n 2 times. Our algorithm
provides a slightly better bound, although Gabow's algorithm is also valid
for a directed multigraph.
Enumerating All Small Cuts
For a given  > 0, let C
denote the set of all -cuts in N satisfying
< . In this case, we do not distinguish cut X from its complement
X. To avoid the duplication of X and V X, therefore, we choose an
arbitrary vertex r 2 V as a reference vertex, and denote by C
r
(N ) the set
of all -cuts
. Note that jC
r
(N )j by
denition, and in what follows, we compute C
r
(N ) to avoid confusion.
We rst give outline of our algorithm for enumerating small cuts. Now,
given a network c) and ordered set
a sequence of networks N i
let N i01
be the network obtained from N i
by isolating vertex
.
denotes the vertices in N i
. In what follows,
we explain a relation between networks N i
and N i01
. Any cut X with
in N i
is also a cut in N i01
, and c(X; N i
holds by Lemma 4.2(a). Also, note that two cuts X and X 0 in N i
such that
becomes the same cut in N i01
(see Fig.3).
Choose v 1 as the reference vertex r. From the above observation, we
see that any cut X 2 C !ff
appears in exactly one of the three sets:
r (N i01
r (N i01 )g or ffv i gg.
In other words,
r (N i01
r (N i01 )g[ffv i gg(6.1)
contains C !ff
Suppose that we have weights of cuts, fc(X; N i01
r (N i01 )g,
and set Q v i
of triplets (u; v; ) that are used to isolate v i in N i . These are
obtained by ISOLATE. For each Y 2 C+v i
r (N i01 )], its weight c(Y
can be easily computed from C !ff
as follows. If
then clearly
r (N i01 ), then we have
such that fu; vg  Y
since c(Y ; N i01 ) decreases by 2 at each edge-splitting (u; v;
such
that Y separates fv i g and fu; vg, by (4.1). Analogously, if
for a Y
r (N i01 ), then
such that fu; vg \ Y
To compute c(Y ; N i ) eciently, we use a data structure that enables us to
check if w 2 Y in O(1) time, e.g., by preparing a membership mapping
from jQ v i
can be computed in
using fc(X; N i01
and a membership mapping f Y .
Consequently, all cuts in C !k(N) (N ) can be enumerated in the following
manner.
Procedure
Input: a network and a positive real k > 1;
do
be the vertex v in N i that minimizes jNB(v;N i )j;
6 Isolate v i in N i by applying procedure ISOLATE;
be the set of triplets (u; v; ) obtained by ISOLATE;
8 Denote the resulting network by N i01
9 end;
do
15 for each X 2 C <
such that fu; vg  Xg;
such that fu; vg \
[C <
r (N j01 )] := C <
[C <
22 output C <k(N
Theorem 6.1 For a network c) and a real number k > 1, ENUMERATE
computes C <k(N correctly, and runs in O(m 2 n+n 2k m) time,
Proof. The correctness of ENUMERATE follows from the discussion so
far, in particular from (6.1) and (6.2). In line 2, -(N ) can be computed
in O(nm the number of edges with
positive weights in N i , n. By Theorem 5.1, m i  m holds for all
i. First consider how many times the operation of weighted edge-splitting is
executed in ISOLATE throughout ENUMERATE. Since each vertex v i to be
isolated minimizes jNB(v;N i )j in N i , we have jQ v i
by Theorem 5.1. Therefore, all N i 's in the rst loop of lines 3-9 can be
constructed in
O(
(n
time. Now we consider the time required for the second for-loop of lines 12-
21. By Lemma 4.2(b),
holds for the networks N i obtained by ISOLATE. Updating the membership
mapping f X for a cut X requires time. It is known
[10] that, for any network N  with i vertices and a real k  1, the number
of cuts with weights less than k(N  ) is O(i 2k ). Hence, jC <
As discussed before the description
of ENUMERATE, each c(X; N i ) for a cut X 2 C+v i
r (N i01 )] can be up-dated
from c(X; N i01 ) in O(jQ v i
time. Then, updating C <
requires
(jC
(i 2k jQ v i
(i
time. Therefore, the entire running time of ENUMERATE is O(mn(m
7 New Bound on the Number of Small Cuts
The objective of this section is to improve the upper bound O(n 2k ) on
obtained by Karger [10] to
for 4. This also improves
the time complexity of ENUMERATE to O(m log n) for such k.
Theorem 7.1 For any network it holds jC < 4(N )
. 2
The proof of this theorem will be given in the latter half of this section.
Here we note that this bound
is also known as a tight upper bound on
the number of minimum cuts in N [1, 3]. In fact, jC <3
is
actually attained by a ring network consisting of n  2 vertices, in which
holds. In this network, there are
minimum cuts and all other
cuts X satisfy c(X)  4 > 4(N ). We also see that coecient is the largest possible for
to be an upper bound. For
this, consider a complete network K 4 with four vertices, where each edge is
weighted 1. Clearly, (K n four 3-cuts and three 4-cuts,
indicating jC
(=
Corollary 7.1 For a network c) and 1 < k  4, C
can be computed in O(m 2 n +mn 2 log n) time. 2
Proof. From the proof of Theorem 6.1, we see that the running time of
fore, by Theorem 7.1, ENUMERATE runs in O(m 2 n+mn 2 log n+
Now we prove Theorem 7.1 via several lemmas.
For a network c) with a designated vertex s 2 V and an
> 0, if two cuts X and X both belong to C
call fX;X
a pair of twin cuts with respect to (s; ). Let r 2 V s be a
reference vertex, and dene
From (6.1), we have
r (N )j  jC
r;s
Based on this inequality, we prove Theorem 7.1 by induction on
The theorem clearly holds for 2. Assume here that Theorem 7.1 holds
for any network with less than n vertices. If we can show
r;s (N )j  n 2; (7.2)
then we have from (7.1) that
r (N )j  jC
r;s
jC
r;s
(from

(induction hypothesis and (7.2))

Therefore, property (7.2) proves Theorem 7.1. The proof of (7.2) will be
given below via Lemmas 7.1-7.5.
Lemma 7.1 For a network c) with a reference vertex r 2 V ,
let X;Y and Z be three distinct cuts in C
r (N ), and dene a partition
of V as follows (see Fig. 4).
Then at least one of W 1 empty, and at least one of
2 and W 0
3 is also empty.
Proof. If none of W 1 empty, then we would have
which is a contradiction. Analogously, since r 2 W 06= ;, one of W 0; W 0and
W 0must be empty. 2
Lemma 7.2 Let c) be a network, and let s 2 V and r 2 V s.
If no two cuts in T C
cross each other, then there are two disjoint
nonempty subsets XA ; XB  V fs; rg such that every cut in T C
separates XA and XB .
Proof.
For a cut
r;s (N ), s-proper cut ~
, from which
From this and c (fsg; X)
r;s (N ) with the smallest cardinality, i.e.,
r;s (N )g:
For any other cut X 2 T C
r;s (N ), X and XA do not cross each other
by the assumption. Then, from the minimality of jXA j, we see
r;s (N
;g. We next choose XB 2 T C A such that
Then, analogously to the above, we can show that
r;s (N
In particular, this implies XA \
Finally, we see that there is no cut Y 2 T C
r;s (N ) such that Y
c (fsg) would follow from (7.5), which is a contradiction. Therefore, any
must separate XA and XB . It is also clear that
If two cuts X i and X j do not cross each other and both separate XA
and XB , then (i)
Lemma 7.3 If no two cuts in T C
cross each other, then
r;s (N )j  n 2.
Proof. Recall that X  V fs; rg for
r;s (N ) from the denition
of T C r . In this case, by Lemma 7.2, any cut X in T C
Therefore, all cuts in
r;s N ) can be numbered as so that
From this, we see
that p  n 2. 2
Lemma 7.4 For a network
X;Y and Z be three cuts in T C
r;s (N ). Dene W i and W 0
as in (7:4). Then at least two of are empty, and at least
two of W 0; W 0and W 0are also empty.
Proof. Since no cut in T C
r;s (N ) contains r, it holds r 2 W4 s. By
lemma 7.1, one of W i (other cases can be
treated analogously). Then consider X
and X
are a pair of twin cuts. Again by applying lemma 7.1 to three cuts
we see that one of must be empty.
one of W 2 ; W 3 and W 4 is also empty. Similar argument
also proves the result for subsets
Lemma 7.5 If there are two cuts in T C
r;s (N ), which cross each
other, then jT C
r;s (N 2.
Proof. Suppose that two cuts X and Y in T C
cross each other.
In this case, if T C
r;s (N ) contains other cut (say Z), then Lemma 7.4
applies to W i and 4). However, this is impossible since two
crossing cuts X and Y have already produced four non-empty subsets among
's. Hence, the third cut Z cannot exist. Thus, jT C
r;s (N
Lemma 7.3 and 7.5 prove property (7.2), which also completes the proof
of Theorem 7.1.

Acknowledgements

The authors are grateful to Professor A. Frank of Eotvos University for
his valuable comments, based on which Lemma 3.1 is established. This re-search
was partially supported by the Scientic Grant-in-Aid from Ministry
of Education, Science and Culture of Japan.



--R

The minimum number of edges and vertices in a graph with edge-connectivity n and m n-bonds
The combinatorics of network reliability
On the structure of a family of minimal weighed cuts in a graph
Augmenting graphs to meet edge-connectivity requirements
On a theorem of Mader
On the edge-connectivity algorithm of Nagamochi and Ibaraki
A note on Nagamochi and Ibaraki's min-cut algorithm and its simple proofs by Stoer

On the number of small cuts
Global min-cuts in RNC

A reduction method for edge-connectivity in graphs
Computing the edge-connectivity of multigraphs and capacitated graphs
A simple and constructive proof of a minimum cut algorithm

A simple min cut algorithm
Their enumera- tion
--TR

--CTR
Lisa K. Fleischer , Adam N. Letchford , Andrea Lodi, Polynomial-Time Separation of a Superclass of Simple Comb Inequalities, Mathematics of Operations Research, v.31 n.4, p.696-713, November 2006
polynomial algorithm;graphs;minimum cuts;edge-splitting