%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% %
% INCLUSION-EXCLUSION AND NETWORK RELIABILITY %
% %
% by %
% %
% Klaus Dohmen %
% Humboldt-Universitaet zu Berlin %
% Institut fuer Informatik %
% Unter den Linden 6 %
% D-10099 Berlin, Germany %
% e-mail: dohmen@informatik.hu-berlin.de %
% WWW: http://www.informatik.hu-berlin.de/~dohmen %
% %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[12pt,dvips]{article}
\usepackage{amsmath,amssymb,epsfig}
\pagestyle{myheadings}
\markright{\sc the electronic journal of combinatorics 5 (1998), \#R36\hfill}
\setlength{\textwidth}{152mm}
\setlength{\textheight}{229mm}
\setlength{\oddsidemargin}{0mm}
\setlength{\evensidemargin}{\oddsidemargin}
\setlength{\topmargin}{0mm}
\setlength{\headsep}{7mm}
\parskip2ex
\newcommand{\proof}{{\bf Proof}.~\,}
\newcommand{\remark}[1]{{\bf Remark{#1}.~\,}}
\newcommand{\remarks}[1]{{\bf Remarks{#1}.~\,}}
\newcommand{\proposition}[1]{{\bf Proposition{#1}.~\,}}
\newcommand{\theorem}[1]{{\bf Theorem{#1}.~\,}}
\newcommand{\corollary}[1]{{\bf Corollary{#1}.~\,}}
\newcommand{\point}{\mbox{~.}}
\newcommand{\comma}{\mbox{~,}}
\newcommand{\Rel}{\mbox{\rm Rel}}
\renewcommand{\Pr}{\mbox{\rm Pr}}
\newcommand{\chains}{\mbox{\rm chains}}
\newcommand{\chainsk}{\mbox{\rm\tiny chains}}
\renewcommand{\refname}{\begin{flushleft}
\large\bf References
\end{flushleft}}
\newcommand{\kdbox}{~\,\rule[-0.5mm]{0.3em}{2ex}}
\renewcommand{\theenumi}{\roman{enumi}}
\renewcommand{\labelenumi}{(\theenumi)}
\setlength{\itemsep}{0ex}
\setlength{\parsep}{0ex}
\begin{document}
\thispagestyle{empty}
\begin{center}
\LARGE
Inclusion-Exclusion and Network Reliability
\vspace{7mm}
\large
Klaus Dohmen\\
Humboldt-Universit\"at zu Berlin\\
Institut f\"ur Informatik\\
Unter den Linden 6\\
D-10099 Berlin, Germany\\
e-mail: {\tt dohmen@informatik.hu-berlin.de}
\vspace{7mm}
\normalsize
Submitted: November 17, 1997; Accepted: June 23, 1998\\
AMS Classification: 60C05, 68M15, 90B12, 90B25
\normalsize\vspace{7mm}
\begin{minipage}{11.5cm}
\begin{center}
\bf Abstract
\end{center}
\small
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.
\end{minipage}
\end{center}
\vspace{2.5mm}
\rm\normalsize
\begin{flushleft}
\large\bf 1. Introduction to network reliability
\end{flushleft}
\parskip2ex
{\parskip0ex
\noindent 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 {\em 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 {\em 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 {\em coherent binary system} is a couple
$\Sigma = (E,\phi)$ consisting of a finite set~$E$
and a function $\phi$ from the power set of $E$ into
$\{0;1\}$ such that $\phi(\emptyset)=0$, $\phi(E)=1$ and
$\phi(X)\le \phi(Y)$ for any $X,Y\subseteq E$ with
$X\subseteq Y$. $E$ and $\phi$ are respectively called
the {\em component set} and the {\em structure function
of\/}~$\Sigma$.
At any instant of time, each component $e$ of $\Sigma$
assumes randomly
and independently one of
two states, {\em operating\/} or {\em failing\/}, with
probabilities $p_e$ and $q_e=1-p_e$, respectively.
$\Sigma$
is said to be {\em operating\/} resp.\ {\em failing\/}
if $\phi$ applied to the set of operating components
gives~$1$ resp.~$0$.
The {\em
reliability of\/} $\Sigma$ is
the probability that $\Sigma$
is operating.
Since this quantity
is determined by $\Sigma$
and ${\bf p}=(p_e)_{e\in E}$, it is
abbreviated to $\Rel_\Sigma({\bf p})$.
A key role in calculating $\Rel_\Sigma({\bf p})$
is played by the
minpaths and mincuts of $\Sigma$:
A {\em minpath of\/} $\Sigma$ is a minimal set $P\subseteq E$ such that
$\phi(P)=1$; that is, $\phi(P)=1$ and $\phi(Q)=0$
for any proper subset $Q$ of $P$.
A {\em mincut of\/} $\Sigma$ is a minimal set $C\subseteq E$ such that
$\phi(E\setminus C)=0$; that is,
$\phi(E\setminus C)=0$ and $\phi(E\setminus 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 $\Sigma = (E,\phi)$,
where $E$ is the edge-set of the network and
$\phi(X)=1$ if and only if $X$ contains the edges
of an $s,t$-path.
For source-to-$T$-terminal reliability we take
$\Sigma = (E,\phi)$, where $E$ is the edge-set of
the network and $\phi(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\in 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\in T$)
of the network.
A common way to compute
the reliability of a network
makes use of
the well-known 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~\cite{Shier1,Shier2}, 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~\cite{Provan}, which provides an algorithm
for computing network reliability
in pseudopolynomial time. Finally, we draw some conclusions to
$k$-out-of-$n$ systems.
}
\vspace{2mm}
\begin{flushleft}\large\bf
2. The new inclusion-exclusion approach
\end{flushleft}\parskip2ex
\noindent The following
improvement of the inclusion-exclusion principle, which was discovered by
the author~\cite{Doh1} by generalizing Whitney's broken circuit theorem~\cite{Whitney}, offers much shorter expansions than the classical counterpart. (The referee recommends the proof as an ``excellent exercise".)
\proposition{~2.1}{\em Let $(\Omega,{\cal A},\Pr)$ be a
probability space, $\cal F$ a finite poset,
$\{A_F\}_{F\in \,\cal F}$ $\subseteq {\cal A}$ and
$\mathfrak{X}$ a set of non-empty subsets of $\cal F$ such that
for any ${\cal X}\in\mathfrak{X}$,
\begin{equation}
\bigcap_{X\in \,{\cal X}} A_X \,\, \subseteq \,\,
A_{F} \label{condition1}
\end{equation}
for some lower bound $F$ of $\cal X$ which is not
contained in $\cal X$. Then
\begin{equation}
\Pr \left( \,\bigcup_{F\in \,{\cal F}} A_F\right) \,\, = \,\,
\sum_{{\cal I}\in\mathfrak{I}\atop {\cal I}\neq\emptyset}
\,\,(-1)^{|{\cal I}|-1} \,\,
\Pr\left(\, \bigcap_{I\in \,{\cal I}} A_I \right) \, ,
\end{equation}
where
\begin{equation}\label{idef}
\mathfrak{I} \,\, := \,\, \left\{ \,
{\cal I}\subseteq {\cal F}\, \left|\,
\mbox{${\cal I}\not\supseteq {\cal X}$ for any
${\cal X}\in\mathfrak{X}$}\right.
\right\} \, .
\end{equation}}
\vspace{-2mm}
In the sequel, capitals in
roman, calligraphic and Fraktur style such as
$M$, $\cal M$ and $\mathfrak{M}$ relate to objects of
the following three types:
\begin{center}
\begin{tabular}{ll}
$M$ & a set of components\\
${\cal M}$ & a set of sets of components\\
$\mathfrak{M}$ & a set of sets of sets of components
\end{tabular}
\end{center}
For any set-system $\cal M$ we use
$\bigcup \cal M$ to denote the union of all sets in $\cal M$.
From Proposition 2.1 we now deduce the main result of this paper:
\theorem{~2.2}{\em
Let $\Sigma=(E,\phi)$ be a coherent binary system, whose
set of minpaths resp.\ mincuts $\cal F$ is equipped with a
partial ordering relation. Further,
let $\mathfrak{X}$ be a set of nonempty subsets of $\cal F$
such that for any ${\cal X}\in\mathfrak{X}$,
\begin{equation}
F \,\, \subseteq \,\, \bigcup \,\cal X
\label{condition2}
\end{equation}
for some lower bound $F$ of $\cal X$ which is not
contained in $\cal X$. Then
\begin{equation} \label{paths}
\,\,\,\,\,\Rel_\Sigma({\bf p}) \,\, = \,\,
\sum_{{\cal I}\in\mathfrak{I}\atop {\cal I}\neq\emptyset}\,\,
(-1)^{|{\cal I}|-1} \!\prod_{e\,\in\,\bigcup {\cal I}}\! p_e \, ,
\end{equation}
respectively
\begin{equation} \label{cuts}
\!\!\!\!\! 1-\Rel_\Sigma({\bf p}) \,\, = \,\,
\sum_{{\cal I}\in\mathfrak{I}\atop {\cal I}\neq\emptyset}\,\,
(-1)^{|{\cal I}|-1} \!\prod_{e\,\in\,\bigcup {\cal I}}\! q_e \, ,
\end{equation}
where in both cases $\mathfrak{I}$ is defined as in Eq.~(\ref{idef}).}
\proof For any $F\in\cal F$, let $A_F$ denote the event
that all components in $F$ are operating resp.\ failing.
Then we have
\begin{equation}
\!\!\!\!\!\! \Rel_{\Sigma}({\bf p}) \,=\,
\Pr\left( \,\bigcup_{F\in\cal F} A_F\right) \quad\,\,
\mbox{resp.}\quad \,\,
1-\Rel_{\Sigma} ({\bf p})\, =\,
\Pr\left( \,\bigcup_{F\in\cal F} A_F\right) \, .
\label{eqa}
\end{equation}
It is easy to see that Eq.~(\ref{condition1}) holds if and only if
Eq.~(\ref{condition2}) holds and that
\begin{equation}
\Pr\left(\, \bigcap_{I\in \,{\cal I}} A_I \right) \, = \,
\prod_{e\,\in\,\bigcup {\cal I}}\! p_e \qquad\!\!\!\mbox{resp.}
\qquad \!\!\!
\Pr\left(\, \bigcap_{I\in \,{\cal I}} A_I \right)\, = \,
\prod_{e\,\in\,\bigcup {\cal I}}\! q_e \, . \label{vor}
\end{equation}
From Eq.~(\ref{eqa}), Proposition~2.1
and Eq.~(\ref{vor}) the result immediately follows.\kdbox
\corollary{~2.3}{\em Let $\Sigma=(E,\phi)$ be a coherent
binary system, whose set of minpaths resp.\ mincuts
$\cal F$ is partially
ordered such that for any $F_1,F_2\in\cal F$,
$F\subseteq F_1\cup F_2$ for some lower bound $F$ of
$F_1$ and $F_2$.
Then
\begin{equation} \label{pathsc}
\,\,\,\,\,\Rel_\Sigma({\bf p}) \,\, = \,\,
\sum_{{\cal I}\in\chainsk({\cal F})\atop {\cal I}\neq\emptyset}\,\,
(-1)^{|{\cal I}|-1} \!\prod_{e\,\in\,\bigcup {\cal I}}\! p_e \, ,
\end{equation}
respectively
\begin{equation} \label{cutsc}
\!\!\!\!\! 1-\Rel_\Sigma({\bf p}) \,\, = \,\,
\sum_{{\cal I}\in\chainsk({\cal F})\atop {\cal I}\neq\emptyset}\,\,
(-1)^{|{\cal I}|-1} \!\prod_{e\,\in\,\bigcup {\cal I}}\! q_e \, ,
\end{equation}
where $\chains({\cal F})$ denotes the set of chains in $\cal F$.}
\proof By setting $\mathfrak{X}$ equal to the set of all
unordered pairs of incomparable elements of $\cal F$,
Corollary~2.3 is deduced from Theorem 2.2.\kdbox
\remark{}The formulae in Corollary 2.3
are due to Shier~\cite{Shier1,Shier2}.
However, Shier additionally requires the maximality
of each lower bound~$F$ and
the convexity of
each set \mbox{${\cal F}_e = \{F\in{\cal F}:e\in 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~\cite{Provan} (see also~\cite{Ball}) and later generalized by Shier~\cite{Shier1,Shier2}.
We now deduce Shier's generalization
from Corollary~2.3.
\corollary{~2.4}{\em Let $\Sigma=(E,\phi)$ be a coherent
binary system, whose set of minpaths resp.\ mincuts
$\cal F$ is partially
ordered such that for any $F_1,F_2\in\cal F$,
$F\subseteq F_1\cup F_2$ for some lower bound $F$ of
$F_1$ and $F_2$, and such that for any $e\in E$,
$\{F\in{\cal F}:e\in F\}$ is a convex subset of~$\cal F$. Then
\begin{displaymath}
\Rel_\Sigma({\bf p}) \,\, = \,\, \sum_{F\in{\cal F}} \Lambda(F,{\bf p})\, ,
\end{displaymath}
respectively
\begin{displaymath}
\!\!\!\!\!\!\!\!\!\!1-\Rel_\Sigma({\bf p}) \,\, = \,\, \sum_{F\in{\cal F}} \Lambda(F,{\bf q})\, ,
\end{displaymath}
where $\Lambda$ is defined recursively by
\begin{displaymath}
\Lambda(F,{\bf x}) \,\, := \,\, \prod_{e\in F} x_e - \sum_{G\prec F} \Lambda(G,{\bf x}) \!\prod_{e\in F\setminus G} \!\!x_e \, .
\end{displaymath}}
\vspace{-2mm}
\proof By induction on the height of $F$ in $\cal F$ we first establish that
\begin{equation}\label{idid}
\Lambda(F,{\bf x})\,\, =\!\!\sum_{{\cal I}\in\chainsk({\cal F})\atop {\cal I}\neq\emptyset,\, \max{\cal I} = F}
\!\!\!(-1)^{|{\cal I}|-1} \prod_{e\,\in\,\bigcup\cal I}\! x_e \, .
\end{equation}
Obviously, this identity holds if $F$ is the
minimum of~$\cal F$. Otherwise, assume that the induction hypothesis
is valid
for all $G\prec F$. It easily follows that
\begin{displaymath}
\Lambda(F,{\bf x}) \,\,= \,\, \prod_{e\in F}x_e \,-\, \sum_{G\prec F} \!
\sum_{{\cal I}\in\chainsk({\cal F})\atop {\cal I}\neq\emptyset,\,
\max{\cal I}=G} \!\!\!(-1)^{|{\cal I}|-1}\prod_{e\,\in\,\bigcup{\cal I}}\!x_e
\prod_{e\in F\setminus G}\!\! x_e \, .
\end{displaymath}
By convexity,
$\bigcup\, ({\cal I}\cup\{ F\})$ is the disjoint union of $\bigcup{\cal I}$
and $F\setminus G$.
Therefore,
\begin{eqnarray*}
\Lambda(F,{\bf x}) & = & \prod_{e\in F}x_e \,-\, \sum_{G\prec F} \!
\sum_{{\cal I}\in\chainsk({\cal F})\atop {\cal I}\neq\emptyset,\,
\max{\cal I}=G} \!\!\!(-1)^{|{\cal I}|-1}\!\!\!
\prod_{e\,\in\,\bigcup ({\cal I}\cup \{F\})}\!\! x_e\\
& = & \prod_{e\in F}x_e \,-\!\!\! \sum_{{\cal I}\in\chainsk({\cal F})\atop
{\cal I}\neq\emptyset,\, \max{\cal I}\prec F} \!\!\!(-1)^{|{\cal I}|-1}
\!\!\!
\prod_{e\,\in\,\bigcup ({\cal I}\cup \{F\})}\!\! x_e\\
& = & \!\!\!\sum_{{\cal I}\in\chainsk({\cal F})\atop {\cal I}\neq\emptyset,\,
\max{\cal I} = F} \!\!\!(-1)^{|{\cal I}|-1} \prod_{e\,\in\,\bigcup{\cal I}}\! x_e \, .
\end{eqnarray*}
Now, Corollary~2.4 immediately follows from Corollary~2.3 and
Eq.~(\ref{idid}).\kdbox
\remarks{}{\parskip0ex
By the technique of dynamic programming, the
above scheme can be transformed into an
algorithm whose
space complexity is $O(|{\cal F}])$ and whose
time complexity is
$O\left( |E|\cdot |{\cal F}|^2\right)$; see Shier~\cite{Shier1} 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~\cite{Shier1,Shier2}:
\begin{enumerate}
\item For $s,t$-cutsets $X$ and $Y$ of an arbitrary network define
\begin{displaymath}
X\preceq Y\quad :\Leftrightarrow \quad
N(X) \subseteq N(Y)\, ,
\label{cutorder}
\end{displaymath}
where $N(X)$ is the set of nodes reachable from $s$ after
removing $X$.
\item For $s,t$-paths $X$ and $Y$ of a planar network define
\begin{displaymath}
X \preceq Y\quad :\Leftrightarrow
\quad \mbox{$X$ lies below $Y$.}
\label{geomorder}
\end{displaymath}
\end{enumerate}
In each case, it is easy to see that a lattice structure
is induced and that
the greatest lower bound $X\wedge Y$ and
the least upper bound $X\vee Y$ are included \mbox{by $X\cup 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,t$-cutsets resp.\
$s,t$-paths are
ordered as just described.
For further details, the reader is referred to
Shier~\cite{Shier1,Shier2}.
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~\cite{Provan}, 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:
\begin{enumerate}
\item[(iii)] For $s,T$-cutsets $X$ and $Y$ of a complete network define
$X\preceq Y$ as in (i).
%\begin{displaymath}
% X\preceq Y\quad :\Leftrightarrow \quad
%N(X) \subseteq N(Y)\, ,
%\end{displaymath}
%where $N(X)$ denotes the set of nodes reachable from $s$ after
%removing $X$.
\end{enumerate}
This partial ordering relation induces a
$\wedge$-semilattice, and it is easy to verify that the
convexity condition holds.
By contradiction, we prove that $X\wedge Y\subseteq X\cup Y$:
Assume that there is an edge
$e\in (X\wedge Y)\setminus (X\cup Y)$, linking some node~$a$
to some node~$b$. Since $X\wedge Y$ is an $s,T$-cutset, we find that
$a\in N(X\wedge Y)$ and $b\notin N(X\wedge Y)$.
Since $N(X\wedge Y)\subseteq N(X)\cap N(Y)$, we have
$a\in N(X)\cap N(Y)$, and since $e\notin X\cup Y$, we also have
$b\in N(X)\cap N(Y)$.
Let
$Z$ be the set of all edges from $N(X\wedge Y)\cup\{ b\}$
to its complement.
Because the network is complete,
$N(Z) = N(X\wedge Y)\cup\{b\}$ and therefore,
$N(Z)\subseteq N(X)\cap N(Y)$.
Since $X$ is an
$s,T$-cutset, $T\not\subseteq N(X)$ and hence,
$T\not\subseteq 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)\subseteq N(X)\cap N(Y)$ we conclude that
$Z\le X\wedge Y$.
On the other hand, $X\wedge Y < Z$, since
$N(X\wedge Y) \subset N(X\wedge Y)\cup\{b\}\subseteq N(Z)$.
We remark that for $s,t$-cutsets of arbitrary networks, the recursive scheme
is due to Provan and Ball~\cite{Provan}, whereupon for $s,T$-cutsets
of complete networks, it is a special case of a result of Ball and Provan~\cite{Ball}.
}
%\vspace{-5mm}
%\begin{center}
% \rule{3in}{0.3pt}
%\end{center}
%---------------------------------------------------------------------------
{\parskip0ex
We finally draw some conclusions to $k$-out-of-$n$ systems.
By definition, a {\em $k$-out-of-$n$ system} is a coherent binary
system $(E,\phi)$ where $|E|=n$ and for any $X\subseteq E$,
$\phi(X)=1$ if and only if $|X|\ge k$.
Note that the minpaths and mincuts of $(E,\phi)$
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
\begin{equation}
X\preceq Y \quad :\Leftrightarrow \quad \mbox{$x\le y$ for all $x\in X$, $y\in Y\setminus X$}\, .
\label{ordnung}
\end{equation}
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,\dots,6\}$ and $k=3$:
\begin{center}
\epsfig{file=network.eps,width=9cm}
%\newline
%{\bf Figure~1:}~\,Hasse diagram for $E=\{1,\dots,6\}$ and $k=3$.
\end{center}
Again, it is easy to see that the convexity condition holds;
moreover, $\mbox{$X\wedge Y$}\subseteq X\cup Y$, since
$X\wedge Y$ consists of the $k$ smallest elements of $X\cup 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.~(\ref{ordnung}).
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,\phi)$ we now consider
the number of terms on the right-hand side of Eq.~(\ref{pathsc}), that is,
the number of non-empty chains in the poset of $k$-subsets of~$E$.
We prove
that this number is equal to $2 f(n-k)-1$, where $f(0):=1$ and
\begin{equation}\label{ft}
f(t) \,\, := \,\, 1 + \sum_{i=0}^{t-1} {t-i+k-1\choose k-1} f(i)
\quad\,\, (t=1,\dots,n-k)\, .
\end{equation}
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 $2 c(\hat{0})$ where
$\hat{0}$ denotes the minimum of the poset.
It remains to show that $c(\hat{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\,+\, \sum_{i=0}^{t-1}\! \sum_{Q\succ P\atop h(Q)=n-k-i} \!\!\!c(Q)
\, = \, 1\, +\, \sum_{i=0}^{t-1}\! \sum_{Q\succ P\atop h(Q)=n-k-i} \!\!\! f(i)
\, = \, 1+\sum_{i=0}^{t-1} s(P,i) f(i) \]
where $s(P,i):=|\{Q\succ P\,|\,h(Q)=n-k-i\}|$ $(i=0,\dots,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) \, = \, {t - i + k-1\choose k-1}\, ,\quad \! c(P) \, = \, 1+\sum_{i=0}^{t-1} {t-i+k-1\choose k-1} f(i) \, = \, f(t) \, .\]
In order to compare the number of terms
in Eq.~(\ref{pathsc}) with the number of terms in
the classical inclusion-exclusion expansion for given $n$ and~$k$,
\mbox{consider the ratio}
\[ r_k(n) \,\, := \,\, \frac{2 f(n-k)-1}{2^{n\choose k}-1}\, .\]
By Eq.~(\ref{ft}) and since
${t-i+k-1 \choose k-1}\le k^{t-i}$
we have
\[ f(t) \,\, \le \,\, 1 \,+ \,\sum_{i=0}^{t-1} \,k^{t-i} f(i) \quad\,\,
(t=0,\dots,n-k) \, , \]
and therefore,
\[ f(t) \,\, \le \,\, 1 \,+ \,k \,\sum_{i=0}^{t-1} \,(2k)^i \,\, = \,\,
1 \,+\, k\, \frac{1-(2k)^t}{1-2k} \quad\,\,(t=0,\dots,n-k) \, . \]
Hence, for fixed~$k$, there are constants $c_1$ and $c_2$ depending only on $k$ such that
\[ r_k(n) \,\, \le \,\, c_1 \frac{(2k)^n}{2^{n\choose k}} \,\, \sim \,\,
c_1 2^{c_2 n - n^k} \, .\]
For $k>1$ we finally conclude that $r_k(n)\rightarrow 0$ as
$n\rightarrow\infty$.
For $n=5,\dots,10$ the numerical values of $r_2(n)$ are
\[
6.5\times 10^{-2},\,\,
7.0\times 10^{-3},\,\,
3.8\times 10^{-4},\,\,
1.0\times 10^{-5},\,\,
1.3\times 10^{-7},\,\,
9.0\times 10^{-10}\, .\]
}
\vspace{-15mm}
\begin{thebibliography}{9}
\bibitem{Ball} {\sc M.~O.~Ball} and {\sc J.~S.~Provan},
Computing $K$-terminal reliability in time polynomial
in the number of $(s,K)$-quasicuts, {\em Fourth Army conference
on applied mathematics and computing}, Army Research Office,
Washington, 1987, 901--907.\vspace{-1mm}
\bibitem{Doh1} {\sc K.~Dohmen}, A note on M\"obius inversion
over power set lattices, {\em Commentat.\ Math.\ Univ.\ Carol.}\
{\bf 38} (1997), 121--124.\vspace{-1mm}
\bibitem{Provan} {\sc J.~S.~Provan} and {\sc M.~O.~Ball},
Computing network reliability in time polynomial
in the number of cuts, {\em Oper.\ Res.}\ {\bf 32} (1984), 516--526.\vspace{-1mm}
\bibitem{Shier1} {\sc D.~R.~Shier}, {\em Network Reliability
and Algebraic Structures}, Clarendon Press, Oxford, 1991, 72--83.\vspace{-1mm}
\bibitem{Shier2} {\sc D.~R.~Shier}, Algebraic Aspects of Computing
Network Reliability, {\em Applications of Discrete Mathematics\/}
(ed.\ R.~D.~Ringeisen and F.~S.~Roberts), SIAM, Philadelphia, 1988, 135--147.
\bibitem{Whitney} {\sc H.~Whitney}, A logical expansion in mathematics,
{\em Bull.\ Amer.\ Math.\ Soc.} {\bf 38} (1932), 572--579.\vspace{-1mm}
\end{thebibliography}
\end{document}