American Journal of Computational Mathematics, 2012, 2, 316-320
http://dx.doi.org/10.4236/ajcm.2012.24043 Published Online December 2012 (http://www.SciRP.org/journal/ajcm)
An Inclusion-Exclusion Algorithm for Network Reliability
with Minimal Cutsets
Yan-Rui Sun, Wei-Yi Zhou
1School of Sciences, Northeastern University, Shenyang, China
2School of Electronic Information, Wuhan University, Wuhan, China
Received August 10, 2012; revised October 9, 2012; accepted October 23, 2012
ABSTRACT
The inclusion-exclusion formula (IEF) is a fundamental tool for evaluating network reliability with known minimal
paths or minimal cuts. However, the formula contains many pairs of terms which cancel. Using the notion of compara-
ble node partitions some properties of canceling terms in IEF are given. With these properties and the thought of “dy-
namic programming” method, a simple and efficient inclusion-exclusion algorithm for evaluating the source-to-terminal
reliability of a network starting with cutsets is presented. The algorithm generates all the non-canceling terms in the
unreliability expression. The computational complexity of the algorithm is


3
On mM , where n and m are the
numbers of nodes and minimal cuts of the given network respectively, M is the number of terms in the final symbolic
unreliability expression th at generated us ing the presented algorithm. Examples are shown to illustrate the effectiveness
of the algorithm.
Keywords: Inclusion-Exclusion Formula; Network Reliability; Minimal Cu tset; Dynamic Programming
1. Introduction
The reliability of a network is an important parameter in
design and operation of networks. There are many meth-
ods to compute the reliability of networks [1,2]. Several
algorithms exist in the literature for evaluating the reli-
ability of a directed graph by inclusion-exclusion formula
(IEF) based on either path (k-tree) enumeration or cutset
enumeration [3-8]. In finding the k- terminal reliability by
IEF there are two approaches, one based on enumeratin g
all k-trees and the other based on enumerating all
k-terminal cuts. If there are m minimal paths (or cuts) in
a graph, there are possible intersection terms in
IEF. However, the number of non-cancelling terms in
IEF is considerably less.
21
m
Starting with the set of paths (or k-trees) of a directed
graph, Satyanarayana and coworkers [5,6] developed
methods of identifying non-cancelling terms in IEF.
They sh owed that the non- canceling terms of the source-
to-terminal reliability correspond one-to-one with the
p-acyclic subgraphs of the given graph. An algorithm
was given for generating all the p-acyclic subgraphs of a
directed graph [5]. Buzacott [3] gave a corresponding
result for the non-cancelling terms in IEF starting with
the set of cuts of a graph. Since each term in the resulting
formula is associated with a partition of the set of nodes
of the graph, it was called the node partition formula.
Find all the node partitions of a graph is a very tedious
work.
Using a lemma (the Lemma 3.4 of [3]) of incompara-
ble node partitions of [3] and characteristics of can celing
terms in IEF, by the thought of “dynamic programming”
method a simple and efficient inclusion-exclusion algo-
rithm is given in this paper for evaluating the source-
to-terminal reliability of a graph based on minimal cuts.
The algorithm generates only the non-canceling terms of
the reliability expression of the graph.
2. Nomenclature, Notation and Assumption
A network is modeled as a directed graph


,GNE
(abbreviated to G) which consists of a set of nodes N and
a set of edges (links) E. A node
s
N is the source of
G and


tN s is the terminal of G.
2.1. Nomenclature
Source to terminal (s – t) reliability: the probability that
the source s is connected to the terminal node t by paths
working edges.
s
t

cut: a subset of edges whose removal divides the
node set of the network into two parts i and Ni N such
that ii NNN

, i
s
N

and i Nt, i.e. the edge set
from to
i
Ni N.
C
opyright © 2012 SciRes. AJCM

Y.-R. SUN, W.-Y. ZHOU 317
Minimal
s
t cut:
s
t cut which no longer re-
mains a
s
t cut if its any edge is removed.
Candidate child set of : an ordered set
i
N


12
,,,
r
ii i
NN N
1,
ii
NN
consisting of all the node sets such
that ,

2,,
jj r12 r
ii
NN Ni
2
.
Incomparable node sets: a pair of node sets and
such that and . 1
N
2
N1 NN21 NN
2.2. Notation
i
N: subset of such that Ni
s
N
i
N: complement of, and
i
Ni tN

,
ii
NN

: cut, i.e. the edge set from to
i
Ni
N
i
C: 1) cut

,
ii
NN
1) event that all the edges of cut fail
i
: 1) union of all the edges of cuts and
C
ij
CC i C
j
C
2) intersection of events and
i
C
j
C
i
U(N : union of i cuts
)
i

: candidate child set of
i
N

Pr : the probability of event


,
G
Qst: source-to-terminal (s – t) unreliability of G
2.3. Assumption
1) G has perfectly reliable nodes and s-independent
2-state (good and failed) edges, and the reliability of each
edge has been given.
2) Let

,
ii
CNN

i
and

,

j
jj
CNN be mincuts
of G, then

,
ij ijij
CNNNN


is also a min-
cut of G.
3. Preliminaries
Let be the set of mincuts of a given
network G where corresponds one-to-one with the

12
,,,
m
CC C
Ci
node set , i.e.
i
N

,
ii
CNNim

(). The s – t 1, 2,,i
unreliability of G, by IEF, can be expressed as


 

 
12
11
1
12
1
,
Pr
Pr Pr
Pr1 Pr
G
m
iij
imi jm
m
ijk m
ijkm
Qst
CC C
CCC
CCCCC C
 

 







(1)
the summations are over all mincuts and mincut combi-
nations.
In formula (1), there exist possible terms. But
it is possible that ij for some , . Indeed
the most vexing problem in reliability analysis using (1)
is the appearance of large numbers of pairs of identical
terms with opposite sign, which cancel. Find the charac-
teristic of canceling terms in (1) is the keystone of an
efficient algorithm. Buzacott gave a simple and very
useful lemma (Lemma 3.4 of Ref. [3]) to identify some
canceling terms in (1).
21
m
UU,ij ij
Lemma 1. Given any two mincuts

,
ii
CNN

i
and


,
j
jj
CNN of G such that and
i
N
j
N are incom-
parable, all terms in IEF containing both and
i
C
j
C
cancel if


,
ij ijij
CNNNN is also a mincut [3].
In formula (1), assume that 12 m
NN N.
According to Lemma 1, (1) can be changed into:




 



12
12
12
12
11
1
1
1
,Pr
Pr Pr
Pr
1Pr
ij
ijk
k
ii i
k
k
Gm
iij
imN N
ijm
ijk
NN N
ijkm
k
ii i
NNN
iiim
QstC CC
CCC
CCC
CC C
 
 

  


   










(2)
the summations are over all mincuts and mincut combi-
nations that satisfy the given conditions.
The terms in (2) can correspond one-to-one the vertex
of the m rooted trees with the following properties.
1) The root vertex of each rooted tree is the vertex i
corresponding to cut set , its weight is , sign is +1.
N
i
CNi
2) Sons of each vertex i in every rooted tree are all
elements in
C


i
N  , each son’s weight is the union of its
father’s weight and the cut set corresponding to this son
vertex, sign is its father’s sign times –1.
For example, let 1234
, NNNN


,
ii
CNNi


1, 2, 3, 4i. Figure 1 are four rooted trees.
In Figure 1(a), tree (N4) has a only vertex, the root
vertex N4. Its weight is C4, sign is 1. In Figure 1(c), tree
(N2)’s root vertex is N2, its weight is C2, sign is 1. N2 has
two sons: N3 and N4. The son vertex N3’s weight equals
to C2C3, sign is –1; N4’s weight equals to C3C4, sign is –1.
N3’s son is N, here N4’s weight equals to C2C3C4, sign is
4




111

 .
The weight with its sign of each node in the rooted
trees one-to-one corresponds with the term in the expres-
sion of formula (2). So we discuss m rooted trees’ gener-
ating. The rooted tree whose root is is denoted as
tree i
N


i
N.
In fact, if we generate the rooted trees in non-increas-
ing order of root’s modulus and generate the sons of each
vertex in non-decreasing order of the son’s modulus, we
can use the trees which have already been generated to
generate the following trees. For example, Figure 1 are
four rooted trees, where tree is a branch of tree

3
N


2
N, tree


2
N and tree

are the branches of
tree

3
N


1
N. If tree


3
N is generated firstly, we can use
the result when we generate tree . And when we

2
N


Y.-R. SUN, W.-Y. ZHOU 318
(b) (c)
N
2
N
3
N
4
N
4
N
3
N
4
N
4
(a)
(d)
N
4
N
1
N
2
N
4
N
4
N
3
N
4
N
3
Figure 1. Rooted sub-trees. (a) Sub-tree(N4); (b) Sub-tree(N3);
(c) Sub-tree(N2); (d) Sub-tree(N1).
generate tree , we can use tree and tree
directly. This is the thought of “dynamic pro-
gramming”. By this thought the process of generating
trees is greatly simplified.

1
N

3
N

2
N

In formula (2) there are still many terms that can can-
cel each other. The properties of canceling terms are dis-
cussed as follow.
Theorem 1. Let

,
iii
be three
mincuts of a directed graph G, 12 , and
. Then for any mincuts
CNN

1, 2,3i
NN3 N
123 13
CCC CC


0
N
1
00
,CN
that and
0
NN

N
444
,N3 CN that of G,
4
N
0123 013
CCCCCCC, .
1234 134
CCCC CCC
Theorem 2. Let

,
ii
CNNi

1, 2,3i be three

mincuts of a directed graph G with 12 . If
123 then doesn’t exist mincut 3
NNN
13
CCC CC


N
00
,CN
23 013
CC CCC
0
of G, 01 such that 01; and
doesn’t exist
NNCC

444
,CNN
3
of G, such that
. 43
NN
1234 1
CCCC CC34
Theorems 1 and 2 imply that if we find out the all
pairs of canceling terms that union of two cuts and three
cuts, i.e. find out all 2 and 3 U with , the all
canceling terms in (2) can be determined.
C
U
2
UU
The following lemma gives a condition that 23
UU

in (2).
Lemma 2. Let

,
iii
be three
minimal cuts of a directed graph G and .
Then if and only if
.
CNN

3


1,2, 3i
12
NNN
13 123
CC CCC

213 2
,NNNN
According to Theorems 1 and 2 and Lemma 2 we give
the generating processes of the trees with above proper-
ties 1) and 2). Such that trees’ vertices correspond with
the non-canceling terms of (2).
4. Algorithm
This section presents an algorithm for efficiently generat-
ing all the non-canceling terms in (2). The algorithm has
four parts, The main part is to generate all trees whose
vertices correspond with the non-canceling t e rm s of (2 ).
4.1. Algorithm
1) Find all the mincuts of the given directed network


,GNE
12
,,NN
12
,,NN
which satisfies assumptions. Let 12
be the mincuts corresponding to the node partitions
, respectively. Order the node partitions as
such that
,,,
m
CC C
,
m
N
,
m
N12 NNm N.
2) Find




1, 2,,
i
Ni m  .
3) Generate m rooted trees by the following Algo-
rithm-Tree, i.e. generate all the non-canceling terms of


,
G
Qst.
4) Sum up the weights with sign of vertices of all the
trees to obtain the symbolic expression of


,
G
Qst.
Finally, we get the symbolic reliability expression of




,1 ,
GG
Rst Qst .
4.2. Algorithm Tree
By theorems 1 and 2, all the pairs of canceling terms in
IEF can be known if we find the canceling terms which
union of two and three cut sets. Using this property an
algorithm “Algorithm Tree” is given. It has two parts:
“Trees Generation” and “Weighted Trees”. It generates
rooted trees in the non-increase order of the root vertex’s
modulus, i.e. generates tree (Nm), tree (Nm-1), ···, tree (N1)
successively.
4.2.1. Trees Generation
We shall give an algorithm to generate all trees as follow.
Algorithm Trees Generation
Input: 1) the node partitions of G: 12
such that ,,,
m
NN N
12 m
NN N and the corresponding
mincuts .
12
2) the candidate child sets:
,,,
m
CC C






1
111121
12
1
,,,,,
,,,,
,,
k
t
kkk kt
mmm
NNN N
NNN N
NNN






.





Output: all the trees.
Begin
Step 1. Generate the first tree

with the only
vertex, i.e. root vertex .


m
N

N
m
Step 2. Generate the second tree with a root
N
1m

Y.-R. SUN, W.-Y. ZHOU 319
vertex and its only son vertex .
1m
Step 3. Suppose that trees
Nm N


mk
1mi
N , 1, 2,,ikm
have been generated. Generate tree

.
N
N 1) The root of tree

is .
mk mk
2) Generate sons (we call them the first-generation
offspring) of :
N
mk
N,1 ,2, ,,,
mk
mk mkmkt
NN N

 



k
N

,,
mk 
mk
(where
,1 ,mk
NN

mk
NN


mk

1
GN
2 ,
,,,
mk
mkmktm
N 

,
,mktm);


1,1,2
,
mk
mk mkmkt
GNNN NN 


 ,

.
3) While do.

1mk
GN

Begin
Denote the element with the minimal modulus in
as ,
mk,mki
N1it


N
.
 
11kmk mk

i,m
GN GN.
Substitute mk ’s son ,mki with treeNN


,mki
N
,mki
N
.
Denote the son set of this vertex as
. Suppose

GN
m
GN
GN

N
1,mki


,,N



12
1,, ,,
ki
kim kim kiki 
,
m
N
 mki
N


(in the
non-decreasing order of their modulus).

0, 1,mki mki
GN

.
For j = 1 to
i
k
Begin
If and

,1
j
mkimk
NGN


,NNN
,,,
j
mkimk mki , then

 1, 1,,
j
mkimki ki
GN GN


m
N

,
;
 

11
j
mkmk i
GN GN

mk N

;
Cut ’s son ,mk N
j
mki and ,mk’s son Ni
N
,
j
mki
N
N
N
with its offspring from current
tree

;
,mki
Else next j
End
If 0,1,mki mki
, then mark ,mki
,
called it still node, denoted as still node
.

GN GN



,mki

N
End.
Step 4. Repeat step 3 until all the trees


,
i
N
have bee n ge nerate d. ,1,m,2,im 1
End.
4.2.2. Weighted Trees
Tree’s weight is defined the sum of root’s and all verti-
ces’ weights with their sign.
In the order of generating trees, starting from each
tree’s root vertex gives each vertex a weight in depth-
first-search. The root’s weight is the all edges of the cut
set corresponding to the root vertex, sign is +1. Each
non-still vertex’s weight equals to the union of its fa-
t
s
Figure 2. Network.
ther’s weight and all the edges of the cut set correspond-
ing this vertex, its sign is its father’s sign times –1. Each
still node’s weight equals to the union of its father’s
weight and the tree’s weight whose root is this vertex and
its sign is its father’s sign times –1.
5. Computational Complexity
The main part of the presented algorithm is “Algorithm
Sub-tree”. It has two parts. One is Sub-trees Generation,
the other is Weighted Sub-trees. The main work of “al-
gorithm Sub-trees Generation” is to determine whether
there exist edges between two sets. It at most needs




1211mm mm 2 comparison op-
erations for each sub-tree. “Weighted sub-trees” runs in


OM
2m
18
2 2
m
, wh ere M is the number of terms in the last sym-
bolic un-reliability expression. In fact, M is more smaller
than . For examp l e ，the network in Figure 2, m = 18,
, but M = 151. For each of sub-trees,
other operations at most take time. It takes
262144

Om


On ti me to find all mincuts, where n is the number of
nodes of a given network. It takes time to find
each candidate child set. So the computational complex-
ity of the presented algorithm is .

Om
On m

3


M
6. Conclusion
This paper presents an efficient algorithm for evaluating
the reliability of network based mincuts. The algorithm
generates all the non-canceling terms in the unreliability
expression. By the thought of “dynamic programming”
method each vertex at most generates two generations
children in every sub-tree. The number of vertices of the
generated sub-trees are more smaller than the number of
non-canceling terms in


,
G
Qst’s expression. The algo-
rithm has smaller time complexity.
REFERENCES
[1] C. J. Colbourn, “The Combinatorics of Network Reliabil-
ity,” Oxford University Press, New York, Oxford, 1987.
[2] M. O. Ball, C. J. Colbourn and J. S. Provan, “Network
Reliability,” Handbook of Operations Research: Network
Models, Elsevier North-Holland, Amsterdam, Vol. 7,
1995, pp. 673-762.

Y.-R. SUN, W.-Y. ZHOU 320
[3] J. A. Buzacott, “Node Partition Formula for Directed
Graph Reliability,” Networks, Vol. 17, No. 2, 1987, pp.
227-240. doi:10.1002/net.3230170207
[4] J. A. Buzacott and S. K. Chang, “Cut Set Intersections
and Node Partition,” IEEE Transactions on Reliability,
Vol. 31, No. 4, 1982, pp. 385-389.
[5] A. Satyanarayana and A. Prabhakar, “New Topological
Formula and Rapid Algorithm for Reliability Analysis of
Complex Networks,” IEEE Transactions on Reliability,
Vol. 27, No. 1, 1978, pp. 82-100.
doi:10.1109/TR.1978.5220266
[6] A. Satyanarayana and J. N. Hagstrom, “A New Algorithm
for Reliability Analysis of Multi-Terminal Networks,”
IEEE Transactions on Reliability, Vol. 30, No. 4, 1981,
pp. 325-334. doi:10.1109/TR.1981.5221103
[7] L. C. Zhao and F. J. Kong, “A New Formula and an Al-
gorithm for Reliability Analysis of Network,” Microelec-
tron Reliability, Vol. 37, No. 4, 1997, pp. 511-518.
[8] W. C. Yeh, “A Greedy Branch-and-Bound Inclusion-Ex-
clusion Algorithm for Calculating the Exact Multi-State
Network Reliability,” IEEE Transactions on Reliability,
Vol. 57, No. 1, 2008, pp. 88-93.
doi:10.1109/TR.2008.916871