Inclusion-Exclusion and Network Reliability

Klaus Dohmen Humboldt-Universität zu Berlin Institut für Informatik Unter den Linden 6 D-10099 Berlin, Germany

           e-mail: dohmen@informatik.hu-berlin.de

Submitted: November 17, 1997; Accepted: June 23, 1998 AMS Classification: 60C05, 68M15, 90B12, 90B25

Abstract

Based on a recent improvement of the inclusion-exclusion principle, we present a new approach to network reliability problems. In particular, we give a new proof of a result of Shier, which expresses the reliability of a network as an alternating sum over chains in a semilattice, and a new proof of a result of Provan and Ball, which provides an algorithm for computing network reliability in pseudopolynomial time. Moreover, some results on k-out-of-n systems are established.

1. Introduction to network reliability

We consider both directed and undirected networks in which nodes are perfectly reliable and edges fail randomly and independently with known probabilities. For such networks, a large variety of reliability measures exists. The two-terminal reliability, for instance, is the probability that a message can pass from a distinguished source node s to a distinguished terminal node t along a path of operating edges. More generally, the source-to-T -terminal reliability is the probability that a message can pass from s to each node of some specified set T along a path of operating edges. For a unified treatment of the different concepts, we prefer to use the general notion of a coherent binary system:

A coherent binary system is a couple Σ = (E, ϕ) consisting of a finite set E and a function ϕ from the power set of E into {0; 1} such that ϕ(∅) = 0, ϕ(E) = 1 and ϕ(X) ≤ ϕ(Y) for any X, Y ⊆ E with X ⊆ Y. E and ϕ are respectively called the component set and the structure function of Σ.

At any instant of time, each component e of Σ assumes randomly and independently one of two states, operating or failing, with probabilities p_{e} and q_{e} = 1 − p_{e}, respectively. Σ is said to be operating resp. failing if ϕ applied to the set of operating components gives 1 resp. 0. The reliability of Σ is the probability that Σ is operating. Since this quantity is determined by Σ and p = (p_{e})_{e∈E}, it is abbreviated to Rel_{Σ}(p).

A key role in calculating Rel_{Σ}(p) is played by the minpaths and mincuts of Σ: A minpath of Σ is a minimal set P ⊆ E such that ϕ(P) = 1; that is, ϕ(P) = 1 and ϕ(Q) = 0 for any proper subset Q of P. A mincut of Σ is a minimal set C ⊆ E such that ϕ(E \ C) = 0; that is, ϕ(E \ C) = 0 and ϕ(E \ D) = 1 for any proper subset D of C.

To illustrate the preceding definitions, consider the reliability measures introduced at the beginning of this section: An appropriate model for two-terminal reliability is a coherent binary system Σ = (E, ϕ), where E is the edge-set of the network and ϕ(X) = 1 if and only if X contains the edges of an s, t-path. For source-to-T -terminal reliability we take Σ = (E, ϕ), where E is the edge-set of the network and ϕ(X) = 1 if and only if X contains the edges of an s, T -tree (= minimal set of edges including an s, t-path for any t ∈ T). Note that for two-terminal reliability, the minpaths and mincuts of the system correspond to the s, t-paths and s, t-cutsets of the network, respectively, whereupon for source-to-T -terminal reliability they respectively correspond to the s, T -trees and s, T -cutsets (= minimal sets of edges including an s, t-cutset for some t ∈ T) of the network.

A common way to compute the reliability of a network makes use of the wellknown inclusion-exclusion principle. In the next section, we present a new approach which is based on a recent improvement of this principle. By this new approach, we obtain a new proof of a result of Shier [4, 5], which expresses the reliability of a network as an alternating sum over chains in a semilattice, as well as a new proof of a result of Provan and Ball [3], which provides an algorithm for computing network reliability in pseudopolynomial time. Finally, we draw some conclusions to k-out-of-n systems.

2. The new inclusion-exclusion approach

The following improvement of the inclusion-exclusion principle, which was discovered by the author [2] by generalizing Whitney’s broken circuit theorem [6], offers much shorter expansions than the classical counterpart. (The referee recommends the proof as an “excellent exercise”.)

Proposition 2.1. Let (Ω, A, Pr) be a probability space, F a finite poset, {A_{F} }_{F ∈ F} ⊆ A and 𝔛 a set of non-empty subsets of F such that for any X ∈ 𝔛,

⋂_{X∈ X} A_{X} ⊆ A_{F}  (1)

for some lower bound F of X which is not contained in X. Then

Pr ( ⋃_{F ∈ F} A_{F} ) = ∑_{{I∈ℑ \atop I≠∅}} (−1)^{|I|−1} Pr ( ⋂_{I∈ I} A_{I}) ,  (2)

where

ℑ := { I ⊆ F | I ⊉ X for any X ∈ 𝔛} .  (3)

In the sequel, capitals in roman, calligraphic and Fraktur style such as M, M and 𝔐 relate to objects of the following three types:

M a set of components
M a set of sets of components
𝔐 a set of sets of sets of components

For any set-system M we use ⋃ M to denote the union of all sets in M.

From Proposition 2.1 we now deduce the main result of this paper:

Theorem 2.2. Let Σ = (E, ϕ) be a coherent binary system, whose set of minpaths resp. mincuts F is equipped with a partial ordering relation. Further, let 𝔛 be a set of nonempty subsets of F such that for any X ∈ 𝔛,

F ⊆ ⋃ X  (4)

for some lower bound F of X which is not contained in X. Then

Rel_{Σ}(p) = ∑_{{I∈ℑ \atop I≠∅}} (−1)^{|I|−1} ∏ ; e ∈ ⋃ Ip_{e} ,  (5)

respectively

1 − Rel_{Σ}(p) = ∑_{{I∈ℑ \atop I≠∅}} (−1)^{|I|−1} ∏ ; e ∈ ⋃ Iq_{e} ,  (6)

where in both cases ℑ is defined as in Eq. (3).

Proof. For any F ∈ F, let A_{F} denote the event that all components in F are operating resp. failing. Then we have

Rel_{Σ}(p) = Pr ( ⋃_{F ∈F} A_{F} ) resp. 1 − Rel_{Σ}(p) = Pr ( ⋃_{F ∈F} A_{F} ) .  (7)

It is easy to see that Eq. (1) holds if and only if Eq. (4) holds and that

Pr ( ⋂_{I∈ I} A_{I}) = ∏ ; e ∈ ⋃ Ip_{e} resp. Pr ( ⋂_{I∈ I} A_{I}) = ∏ ; e ∈ ⋃ Iq_{e} .  (8)

From Eq. (7), Proposition 2.1 and Eq. (8) the result immediately follows.

Corollary 2.3. Let Σ = (E, ϕ) be a coherent binary system, whose set of minpaths resp. mincuts F is partially ordered such that for any F_{1}, F_{2} ∈ F, F ⊆ F_{1} ∪ F_{2} for some lower bound F of F_{1} and F_{2}. Then

Rel_{Σ}(p) = ∑_{{I∈chains(F) \atop I≠∅}} (−1)^{|I|−1} ∏ ; e ∈ ⋃ Ip_{e} ,  (9)

respectively

1 − Rel_{Σ}(p) = ∑_{{I∈chains(F) \atop I≠∅}} (−1)^{|I|−1} ∏ ; e ∈ ⋃ Iq_{e} ,  (10)

where chains(F) denotes the set of chains in F.

Proof. By setting 𝔛 equal to the set of all unordered pairs of incomparable elements of F, Corollary 2.3 is deduced from Theorem 2.2.

Remark. The formulae in Corollary 2.3 are due to Shier [4, 5]. However, Shier additionally requires the maximality of each lower bound F and the convexity of each set F_{e} = {F ∈ F : e ∈ F }. In fact, these requirements are needed by a recursive scheme, on which Shier’s proof (which is entirely different from ours) is based. This recursive scheme was first established in a less general form by Provan and Ball [3] (see also [1]) and later generalized by Shier [4, 5]. We now deduce Shier’s generalization from Corollary 2.3.

Corollary 2.4. Let Σ = (E, ϕ) be a coherent binary system, whose set of minpaths resp. mincuts F is partially ordered such that for any F_{1}, F_{2} ∈ F, F ⊆ F_{1} ∪ F_{2} for some lower bound F of F_{1} and F_{2}, and such that for any e ∈ E, {F ∈ F : e ∈ F } is a convex subset of F. Then

Rel_{Σ}(p) = ∑_{F ∈F} Λ(F, p) ,

respectively

1 − Rel_{Σ}(p) = ∑_{F ∈F} Λ(F, q) ,

where Λ is defined recursively by

Λ(F, x) := ∏_{e∈F} x_{e} − ∑_{G≺F} Λ(G, x) ∏_{e∈F \G}x_{e} .

Proof. By induction on the height of F in F we first establish that

Λ(F, x) = ∑_{I∈chains(F) I≠∅, max I=F}(−1)^{|I|−1} ∏ ; e ∈ ⋃ Ix_{e} .  (11)

Obviously, this identity holds if F is the minimum of F. Otherwise, assume that the induction hypothesis is valid for all G ≺ F. It easily follows that

Λ(F, x) = ∏_{e∈F} x_{e} − ∑_{G≺F} ∑_{I∈chains(F) I≠∅, max I=G}(−1)^{|I|−1} ∏ ; e ∈ ⋃ Ix_{e} ∏_{e∈F \G}x_{e} .

By convexity, ⋃ (I ∪ {F }) is the disjoint union of ⋃ I and F \ G. Therefore,

Λ(F, x) = ∏_{e∈F} x_{e} − ∑_{G≺F} ∑_{I∈chains(F) I≠∅, max I=G}(−1)^{|I|−1} ∏ ; e ∈ ⋃(I∪{F })x_{e}

= ∏_{e∈F} x_{e} − ∑_{I∈chains(F) I≠∅, max I≺F}(−1)^{|I|−1} ∏ ; e ∈ ⋃(I∪{F })x_{e}

= ∑_{I∈chains(F) I≠∅, max I=F}(−1)^{|I|−1} ∏ ; e ∈ ⋃ Ix_{e} .

Now, Corollary 2.4 immediately follows from Corollary 2.3 and Eq. (11).

Remarks. By the technique of dynamic programming, the above scheme can be transformed into an algorithm whose space complexity is O(|F]) and whose time complexity is O (|E| · |F|^{2}); see Shier [4] for details. Thus, the algorithm is pseudopolynomial, that is, its computation time is bounded by a polynomial in the size of the network and the number of minpaths resp. mincuts.

In order to apply the results to network reliability problems, an appropriate partial ordering relation must be chosen first. The following partial ordering relations on the set of s, t-cutsets and s, t-paths are adapted from Shier [4, 5]:

(i) For s, t-cutsets X and Y of an arbitrary network define

X ⪯ Y :⇔ N(X) ⊆ N(Y) ,

where N(X) is the set of nodes reachable from s after removing X.

(ii) For s, t-paths X and Y of a planar network define

X ⪯ Y :⇔ X lies below Y.

In each case, it is easy to see that a lattice structure is induced and that the greatest lower bound X∧Y and the least upper bound X∨Y are included by X ∪ Y. Moreover, both partial ordering relations satisfy the convexity condition of Corollary 2.4. We conclude that Corollary 2.3 and Corollary 2.4 can be applied to networks whose s, tcutsets resp. s, t-paths are ordered as just described. For further details, the reader is referred to Shier [4, 5].

In general, it is hard to find a partial ordering relation on the set of s, t-paths or s, T -cutsets of a directed network such that the requirements of Corollary 2.4 are satisfied, since otherwise we would have an algorithm for computing two-terminal resp. source-to-T -terminal reliability whose time complexity is bounded by a polynomial in the network size and the number of s, t-paths resp. s, T -cutsets. By a result of Provan and Ball [3], such an algorithm cannot exist unless P = NP.

For complete networks, however, we easily find a partial ordering relation on the set of s, T -cutsets that satisfies the requirements of Corollary 2.4:

(iii) For s, T -cutsets X and Y of a complete network define X ⪯ Y as in (i).

This partial ordering relation induces a ∧-semilattice, and it is easy to verify that the convexity condition holds. By contradiction, we prove that X ∧ Y ⊆ X ∪ Y: Assume that there is an edge e ∈ (X ∧ Y) \ (X ∪ Y), linking some node a to some node b. Since X ∧ Y is an s, T -cutset, we find that a ∈ N(X ∧ Y) and b ∉ N(X ∧ Y). Since N(X ∧ Y) ⊆ N(X) ∩ N(Y), we have a ∈ N(X) ∩ N(Y), and since e ∉ X ∪ Y, we also have b ∈ N(X) ∩ N(Y). Let Z be the set of all edges from N(X ∧ Y) ∪ {b} to its complement. Because the network is complete, N(Z) = N(X∧Y)∪{b} and therefore, N(Z) ⊆ N(X) ∩ N(Y). Since X is an s, T -cutset, T ⊈ N(X) and hence, T ⊈ N(Z). Therefore, Z includes an s, T -cutset, and because the network is complete, Z must be an s, T -cutset itsself. From N(Z) ⊆ N(X) ∩ N(Y) we conclude that Z ≤ X ∧ Y. On the other hand, X ∧ Y < Z, since N(X ∧ Y) ⊂ N(X ∧ Y) ∪ {b} ⊆ N(Z).

We remark that for s, t-cutsets of arbitrary networks, the recursive scheme is due to Provan and Ball [3], whereupon for s, T -cutsets of complete networks, it is a special case of a result of Ball and Provan [1].

We finally draw some conclusions to k-out-of-n systems. By definition, a k-out-of-n system is a coherent binary system (E, ϕ) where |E| = n and for any X ⊆ E, ϕ(X) = 1 if and only if |X| ≥ k. Note that the minpaths and mincuts of (E, ϕ) are the k-subsets and (n − k + 1)-subsets of E, respectively.

Now, let E be totally ordered, and for k-subsets X and Y of E define

X ⪯ Y :⇔ x ≤ y for all x ∈ X, y ∈ Y \ X .  (12)

Thus, a partial ordering relation on the set of k-subsets of E is established. The following figure shows the Hasse diagram for E = {1, …, 6} and k = 3:

Again, it is easy to see that the convexity condition holds; moreover, X ∧ Y ⊆ X ∪Y, since X ∧ Y consists of the k smallest elements of X ∪ Y. Therefore, the minpath versions of Corollary 2.3 and Corollary 2.4 can be applied to k-out-of-n systems whose k-subsets are ordered as in Eq. (12). We conclude that for fixed k, the time and space complexity of the pseudopolynomial algorithm, when applied to k-subsets, is O(n^{2k+1}), respectively O(n^{k}).

For k-out-of-n systems (E, ϕ) we now consider the number of terms on the righthand side of Eq. (9), that is, the number of non-empty chains in the poset of k-subsets of E. We prove that this number is equal to 2f(n − k) − 1, where f(0) := 1 and

f(t) := 1 + ∑_{i=0}^{t−1} \binom{t − i + k − 1}{k − 1}f(i) (t = 1, …, n − k) .  (13)

Note that f(t) depends on k. For any k-subset P of E, let c(P) denote the number of chains extending upward from P. Then, the total number of chains is 2c(ˆ0) where ˆ0 denotes the minimum of the poset. It remains to show that c(ˆ0) = f(n − k). More generally, by induction on t we prove that h(P) = n − k − t entrains c(P) = f(t), where h(P) denotes the height of P. For t = 0 this is clear, since n − k is the maximum height. Now let the height of P be n − k − t where t > 0. By the induction hypothesis we find that

c(P) = 1 + ∑_{i=0}^{t−1} ∑_{{Q≻P \atop h(Q)=n−k−i}}c(Q) = 1 + ∑_{i=0}^{t−1} ∑_{{Q≻P \atop h(Q)=n−k−i}}f(i) = 1 + ∑_{i=0}^{t−1} s(P, i)f(i)

where s(P, i) := |{Q ≻ P | h(Q) = n − k − i}| (i = 0, …, t − 1). We conclude that s(P, i) = s(P, i + 1)(t − i + k − 1)/(t − i), where s(P, t) := 1, and therefore,

s(P, i) = \binom{t − i + k − 1}{k − 1} , c(P) = 1 + ∑_{i=0}^{t−1} \binom{t − i + k − 1}{k − 1}f(i) = f(t) .

In order to compare the number of terms in Eq. (9) with the number of terms in the classical inclusion-exclusion expansion for given n and k, consider the ratio

r_{k}(n) := \frac{2f(n − k) − 1}{2^{\binom{n}{k}} − 1} .

By Eq. (13) and since \binom{t−i+k−1}{k−1} ≤ k^{t−i} we have

f(t) ≤ 1 + ∑_{i=0}^{t−1} k^{t−i}f(i) (t = 0, …, n − k) ,

and therefore,

f(t) ≤ 1 + k ∑_{i=0}^{t−1} (2k)^{i} = 1 + k \frac{1 − (2k)^{t}}{1 − 2k} (t = 0, …, n − k) .

Hence, for fixed k, there are constants c_{1} and c_{2} depending only on k such that

r_{k}(n) ≤ c_{1} \frac{(2k)^{n}}{2^{\binom{n}{k}}} ∼ c_{1}2^{c_{2}n−n^{k}} .

For k > 1 we finally conclude that r_{k}(n) → 0 as n → ∞. For n = 5, …, 10 the numerical values of r_{2}(n) are

6.5 × 10^{−2}, 7.0 × 10^{−3}, 3.8 × 10^{−4}, 1.0 × 10^{−5}, 1.3 × 10^{−7}, 9.0 × 10^{−10} .

References

[1] M. O. Ball and J. S. Provan, Computing K-terminal reliability in time polynomial in the number of (s, K)-quasicuts, Fourth Army conference on applied mathematics and computing, Army Research Office, Washington, 1987, 901–907.

[2] K. Dohmen, A note on Möbius inversion over power set lattices, Commentat. Math. Univ. Carol. 38 (1997), 121–124.

[3] J. S. Provan and M. O. Ball, Computing network reliability in time polynomial in the number of cuts, Oper. Res. 32 (1984), 516–526.

[4] D. R. Shier, Network Reliability and Algebraic Structures, Clarendon Press, Oxford, 1991, 72–83.

[5] D. R. Shier, Algebraic Aspects of Computing Network Reliability, Applications of Discrete Mathematics (ed. R. D. Ringeisen and F. S. Roberts), SIAM, Philadelphia, 1988, 135–147.

[6] H. Whitney, A logical expansion in mathematics, Bull. Amer. Math. Soc. 38 (1932), 572–579.