 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 Email: yanruisun@126.com, weiyi0564@126.com 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 3On 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. 21m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 . Buzacott  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 ) of incompara- ble node partitions of  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 sN 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. st cut: a subset of edges whose removal divides the node set of the network into two parts i and NiN such that iiNNN, isN and iNt, i.e. the edge set from to iNiN. Copyright © 2012 SciRes. AJCM Y.-R. SUN, W.-Y. ZHOU 317Minimal st cut: st cut which no longer re- mains a st cut if its any edge is removed. Candidate child set of : an ordered set iN12,,,rii iNN N 1,iiNN consisting of all the node sets such that , 2,,jj r12 riiNN Ni2. Incomparable node sets: a pair of node sets and such that and . 1N2N1NN21NN2.2. Notation iN: subset of such that NisN iN: complement of, and iNitN ,iiNN: cut, i.e. the edge set from to iNiN iC: 1) cut,iiNN 1) event that all the edges of cut fail i: 1) union of all the edges of cuts and CijCC iCjC 2) intersection of events and iCjC iU(N: union of i cuts )i: candidate child set of iNPr : the probability of event  ,GQst: 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 ,iiCNNi and ,jjjCNN be mincuts of G, then ,ij ijijCNNNN 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,,,mCC CCinode set , i.e. iN,iiCNNim (). The s – t 1, 2,,iunreliability of G, by IEF, can be expressed as 12111121,PrPr PrPr1 PrGmiijimi jmmijk mijkmQstCC CCCCCCCCC 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. ) to identify some canceling terms in (1). 21mUU,ij ijLemma 1. Given any two mincuts ,iiCNNi and ,jjjCNN of G such that and iNjN are incom- parable, all terms in IEF containing both and iCjC cancel if ,ij ijijCNNNN is also a mincut . In formula (1), assume that 12 mNN N. According to Lemma 1, (1) can be changed into: 1212121211111,PrPr PrPr1Prijijkkii ikkGmiijimN NijmijkNN Nijkmkii iNNNiiimQstC CCCCCCCCCC 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. NiCNi2) Sons of each vertex i in every rooted tree are all elements in CiN, 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,iiCNN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 iNiN. 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 3N2N, tree 2N and tree  are the branches of tree 3N1N. If tree 3N is generated firstly, we can use the result when we generate tree . And when we 2NCopyright © 2012 SciRes. AJCM Y.-R. SUN, W.-Y. ZHOU 318 (b) (c) N2 N3 N4 N4 N3 N4 N4 (a) (d) N4 N1 N2 N4 N4 N3 N4 N3 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. 1N3N2N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3N123 13CCC CC0N100,CN that and 0NNN444,N3CN that of G, 4N0123 013CCCCCCC, . 1234 134CCCC CCCTheorem 2. Let ,iiCNNi1, 2,3i be three mincuts of a directed graph G with 12 . If 123 then doesn’t exist mincut 3NNN13CCC CCN00,CN23 013CC CCC0 of G, 01 such that 01; and doesn’t exist NNCC444,CNN3 of G, such that . 43NN1234 1CCCC CC34Theorems 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 3U with , the all canceling terms in (2) can be determined. CU2UUThe following lemma gives a condition that 23UU 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12NNN13 123CC 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 ,GNE12,,NN12,,NN which satisfies assumptions. Let 12 be the mincuts corresponding to the node partitions , respectively. Order the node partitions as such that ,,,mCC C,mN,mN12NNmN. 2) Find 1, 2,,iNi m. 3) Generate m rooted trees by the following Algo-rithm-Tree, i.e. generate all the non-canceling terms of ,GQst. 4) Sum up the weights with sign of vertices of all the trees to obtain the symbolic expression of ,GQst. Finally, we get the symbolic reliability expression of ,1 ,GGRst 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 ,,,mNN N12 mNN N and the corresponding mincuts . 122) the candidate child sets: ,,,mCC C1111121121,,,,,,,,,,,ktkkk ktmmmNNN NNNN NNNN. Output: all the trees. Begin Step 1. Generate the first tree with the only vertex, i.e. root vertex . mNNmStep 2. Generate the second tree with a root N1mCopyright © 2012 SciRes. AJCM Y.-R. SUN, W.-Y. ZHOU 319vertex and its only son vertex . 1mStep 3. Suppose that treesNmNmk1miN , 1, 2,,ikmhave been generated. Generate tree. NN1) The root of tree is . mk mk2) Generate sons (we call them the first-generation offspring) of : NmkN,1 ,2,,,,mkmk mkmktNN N kN,,mk mk (where ,1 ,mkNNmkNNmk1GN2 ,,,,mkmkmktmN, ,mktm); 1,1,2,mkmk mkmktGNNN NN ,. 3) While do. 1mkGNBegin Denote the element with the minimal modulus in as , mk,mkiN1itN.  11kmk mki,mGN GN. Substitute mk’s son ,mki with treeNN,mkiN,mkiN. Denote the son set of this vertex as . Suppose GNmGNGNN1,mki,,N121,, ,,kikim kim kiki ,mNmkiN (in the non-decreasing order of their modulus). 0, 1,mki mkiGN. For j = 1 to ikBegin If and ,1jmkimkNGN,NNN,,,jmkimk mki , then 1, 1,,jmkimki kiGN GNmN,;  11jmkmk iGN GNmkN; Cut ’s son ,mkNjmki and ,mk’s son NiN,jmkiNNN 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 ,iN have bee n ge nerate d. ,1,m,2,im 1End. 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 OM2m182 2m, 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 . OmOn m3M6. 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 ,GQst’s expression. The algo- rithm has smaller time complexity. REFERENCES  C. J. Colbourn, “The Combinatorics of Network Reliabil-ity,” Oxford University Press, New York, Oxford, 1987.  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. Copyright © 2012 SciRes. AJCM Y.-R. SUN, W.-Y. ZHOU Copyright © 2012 SciRes. AJCM 320  J. A. Buzacott, “Node Partition Formula for Directed Graph Reliability,” Networks, Vol. 17, No. 2, 1987, pp. 227-240. doi:10.1002/net.3230170207  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.  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  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  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.  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