数理解析研究所講究録
第 833 巻 1993 年 80-90

80

A Lower Bound of the Expected Maximum Number ofEdge-disjoint s-t Paths on Probabilistic Graphs
程鵬

増山繁Peng CHENG

Shigeru MASUYAMA

豊橋技術科学大学知識情報工学系
Department of Knowledge-Based Information Engineering,
Toyohashi University of Technology,
Toyohashi-shi 441, Japan
Abstract

For a probabilistic graph $(G=(V, E, s, t),p)$ , whereis an undirected graph with specified
source vertex and sink vertex $t(s\neq t)$ in which each edge has independent failure probability andeach vertex is assumed to be failure-free, and $p=(p(e_{1}), \ldots, p(e_{|E|}))$ is a vector consisting of failure
probabilities $p(e;)s$ of all edges
in , we consider the problem of computing the expectedof edge-disjoint s-t paths. It has been known that this computing
maximum number
problem is NP-hard even if is restricted to several classes like planar graphs, s-t out-in bitrees
and s-t complete multi-stage graphs. In this paper, for a probabilistic graph $(G=(V, E, s, t), p)$ ,we propose a lower bound ofand show the necessary and sufficient conditions by which thelower bound coincides with
. Furthermore, we also give a method of computing the lower
for a probabilistic graph $(G=(V, E, s, t), p)$ .
bound of
$G$

$s$

$E$

$e_{i}s$$\Gamma_{(G,p)}$$G$$\Gamma_{(G,p)}$$\Gamma_{(G,p)}$$\Gamma_{(G,p)}$1

Introduction

is an undirected graph with specified
We consider a probabilistic graph $(G=(V, E, s,t),p)$ , where
source vertex and sink vertex $t(s\neq t)$ in which each edge has independent failure probability andeach vertex is assumed to be failure-free, and $p=(p(e_{1}), \ldots,p(e_{|E|}))$ is a vector consisting of failure
probabilities $p(e_{i})s$ of all edges
in . The expected maximum numberof edge-disjoint
s-t paths (namely, s-t paths having no edge in common) in a probabilistic graph $(G,p)$ is usefulfor network reliability analysis. Note that the problem of computing , t-connectedness $[1,3]$ , namely,
probability that there exists at least one operative s-t path, is a special case of computing
ina probabilistic graph $(G,p)$ .
However, it is known that the problem of computing
in a probabilistic graph $(G,p)$ is
NP-hard, even if
is restricted to several classes, e.g., planar graphs, s-t out-in bitrees and s-t, it is interesting for us to find its lower
complete multi-stage graphs [2]. Thus, for estimatingbound in a probabilistic graph $(G,p)$ .
using an s-t path number function of for a
In this paper, we define a lower bound of
probabilistic graph $(G,p)$ , and give the necessary and sufficient conditions by which this lower boundcoincides withand a method of computing this lower bound. This paper is organized as follows:
Graph theoretic terminologies used throughout this paper are described in section 2. A lower boundofin a probabilistic graph $(G,p)$ is defined in section 3. Section 4 shows the necessary andsufficient conditions by which this lower bound coincides with
. Furthermore, we suggest amethod of computing the lower bound in section 5.
$G$

$s$

$e_{i}’ s$$E$$\Gamma_{(G,p)}$$s$$\Gamma_{(G,p)}$$\Gamma_{(G,p)}$$G$$\Gamma_{(G,p)}$$G$$\Gamma_{(G,p)}$$\Gamma_{(G,p)}$$\Gamma_{(G,p)}$$\Gamma_{(G,p)}$812Preliminaries

2.1

Graph Theoretic Terminologies

A two-terminal undirected graph $G=(V, E, s, t)$ consists of a finite vertex set and a set of pairsof vertices, called edges, where and , called source and sink, respectively, are two specified distinct
vertices of . For an edge $(u, v)$ , the two vertices and are said to be end vertices of $(u, v)$ , and$(u, v)$ is aid to be incident toand .
In $G=(V, E, s,t)$ , an x-y path of length from vertex to vertex is an alternating sequenceof vertices $v_{i}\in V(0\leq i\leq k)$ and edges $(v_{i-1}, v_{i})\in E(1\leq i\leq k)$ ,
$E$

$V$

$t$

$s$

$V$

$u$

$u$

$s$

$v$

$v$

$k$

$\pi$

$\pi:(x=)v_{0},$ $(v_{0}, v_{1}),$ $v_{1},$$x$$\ldots,$$y$$v_{k-1},$ $(v_{k-1}, v_{k}),$ $v_{k}(=y)$,

where vertices $v_{i}’ s(0\leq i\leq k)$ are distinct. i.e., a path denotes a simple path throughout this paper.
For short, we also denote an x-y path by$\pi$$\pi:(x=)v_{0},$ $v_{1},$$\ldots,$$v_{k-1},$ $v_{k}(=y)$.

The vertices
are called its internal vertices and the vertices $v_{0}(=s),$ $v_{k}(=t)$ are called its
end vertices. Let $V(\pi),$ $E(\pi)$ denote the set of all vertices and the set of all edges on an x-y path ,respectively. The set of all x-y paths in is denoted by $P_{xy}(G)$ . Paths
are called internalvertex-disjoint paths if they have no vertex in common except their end vertices. s-t paths
are called edge-disjoint s-t paths if any two of them have no edge in common, and the maximum
number of edge-disjoint s-t paths in
is denoted by.
A graph $G_{1}=(V_{1}, E_{1})$ is a subgraph of $G=(V, E, s,t)$ , ifandhold. Ifis$E’\subseteq
E$a subgraph of , other than itself, thenis a proper subgraph of . For a subset, thesubgraph derived from by deleting all edges of $E’$ is denoted by $G-E’(=(V, E-E’, s,t))$ . A
subset $E’(\subseteq E)$ is called an s-t edge-cutset if $G-E’$ has no s-t path. An s-t pathis an s-t
edge-cut-path if $E(\pi)$ is an s-t edge-cutset. An s-t edge-cutset with the minimum cardinality amongs-t edge-cutsets of is said to be minimum. By well-known Menger’s theorem [4],is equal tothe cardinality of a minimum s-t edge-cutset of for any .
$v_{1},$$\ldots,$$v_{k-1}$

$\pi$

$G$

$\pi_{1},$$\pi_{r}$$\ldots,$$\pi_{1},$$G$$\pi_{f}$$\lambda_{st}(G)$$E_{1}\subseteq E$$V_{1}\subseteq V$

$G$

$G$

$\ldots,$$G_{1}$$G$$G_{1}$

$G$

$\pi$

$G$

$\lambda_{st}(G)$

$G$

$G$

Probabilistic Graph

2.2

A probabilistic graph, denoted by $(G=(V, E, s,t),p)$ , or $(G,p)$ , for short, is defined as follows:(i) $G=(V, E, s,t)$ is a two-terminal graph, where each edgeofis in either of the following two
states: failed or operative (not failed), having known independent failure probability $p(e),$ $0\leq p(e)\leq 1$(or operative probability $q(e)=1-p(e)$ ), and each vertex is as sumed to be failure-free.
(1i)
is a vector consisting of all edge failure probabilities $p(e))s$ in .
$e$

$E$

$E$

$p$

Fora probabilistic graph(G $=(V,$ $E,$ $s,t),p$ ), $letasubgraphG-U(\subseteq E)$ correspond to an eventthat all edges ofare failed and all edges of $E-U$ are operative. Clearly, the probability$\rho(G-U)$ of arising a subgraph $G-U(\subseteq E)$ is computed by the following formula.
$\mathcal{E}_{U}$$U$$\rho(G-U)=\prod_{e\in U}p(e)\prod_{e\in E-U}q(e)(=1-p(e))$

Furthermore, $\sum_{U\subseteq E}\rho(G-U)=1$ holds.
Now, we define the expected maximum number
graph $(G=(V, E, s, t),p)$ as follows:$\Gamma_{(G,p)}$.

of edge-disjoint s-t paths in a probabilistic$\Gamma_{(G,p)}\equiv\sum_{U\subseteq E}\lambda_{st}(G-U)\rho(G-U)$

.

(1)

82
It is known that the problem of computing
for a probabilistic graph $(G,p)$ is NP-hard,even if is restricted to several special classes like planar graphs, s-t out-in bitrees and s-t multistage complete graphs, etc. [2]. Thus, it is interesting for us to consider a lower bound offorestimating it.
$\Gamma_{(G,p)}$$G$$\Gamma_{(G,p)}$3

A Lower Bound of$\Gamma_{(G,p)}$We define a lower bound of the expected maximum number of edge-disjoint s-t paths in a probabilistic
graph.
An s-t path number function of $G=(V, E, s, t)$ is a one-to-one integral function : $P_{st}(G)-\succ$. The s-t pathwith $f(\pi)=k$ is said to be the s-t path of number , and denoted by .
The s-t path with the minimum number in $G-E’(\subseteq E)$ with respect tois denoted by $\pi_{m(G-E’,f)}$ .
First, we give the following procedure FEDP to find edge-disjoint s-t paths in $G=(V, E, s,t)$ .
$f$$\{1, \ldots, l\}$

$f$

$k$

$\pi$

$\pi_{k}$$f$Procedure FEDP
Input A graph $G=(V, E, s, t)$ and an s-t path number function
Output The set of edge-disjoint s-t paths FEDP $(G, f)$ .

of

$f$

$G$

.

BEGIN
$G’$

$:=G;FEDP(G, f):=\phi$ ;WHILE $P_{st}(G’)\neq\phi$ DO
BEGIN
Find $\pi_{m(G’,f)}$ from $P_{st}(G’)$ ;FEDP $(G, f)$ $:=FEDP(G, f)\cup\{\pi_{m(G^{l},f)}\}$ ;$G’$$:=G’-E(\pi_{m(G’,f)})$END;
Output FEDP $(G, f)$

END.

口

It is clear that FEDP $(G, f)$ obtained by FEDP is a set of edge-disjoint s-t paths in
the following formula holds.
$|FEDP(G, f)|\leq\kappa_{st}(G)$,for any

$G,$

$f$

$G$

. Namely,.

(2)

For a probabilistic graph $(G=(V, E, s,t),p)$ and an s-t path number function
define the value
as follows:

$f$

of

$G$

, we now$\underline{\Gamma}_{(G,f,p)}$$\underline{\Gamma}_{(G,f,p)}\equiv\sum_{U\subseteq E}|FEDP(G-U, f)|\rho(G-U)$

By formulas (1),(2),(3),$\underline{\Gamma}_{(G,f,p)}$is a lower bound of$\underline{\Gamma}_{(G,j,p)}\leq\Gamma_{(G,p)}$4,$\Gamma_{(G,p)}$for any(3).

, namely, the following formula holds.

$G,$

$f,$

$p$

.

Necessary and Sufficient Conditions

In this section, we give the necessary and sufficient conditions by which
in a probabilistic graph $(G,p)$ .

$\underline{\Gamma}_{(G,j,p)}$coincides with$\Gamma_{(G,p)}$83
A Necessary and Sufficient Condition of an s-t Path Number Function

4.1

By formulas (1),(2),(3), the following Theorem 4.1 immediately holds.
holds iff
Theorem 4.1. Given $(G=(V, E, s,t),p)$ , thenfunction satisfying the following formula.
$\underline{\Gamma}_{(G,f,p)}=\Gamma_{(G,p)}$$G$

has an s-t path number$f$$|FEDP(G-U, f)|=\lambda_{st}(G-U)$ ,for any$U\subseteq E$

.

(4)

口

Definition 4.1. An s-t path number function

$f$

of

$G$

is called exact if$f$satisfies formula (4).

$\square$is
A graph $G=(V, E, s, t)$ is said to be s-t k-edge-connected if $\lambda_{st}(G)=k$ holds. A graph. A graphis said to be -edge-cut s-t
said to be -edge-cut if is an s-t edge-cut-path inis s-t 2-edge-connected. A -edge-cut
2-edge-connected if
is an s-t edge-cut-path ofands-t 2-edge-connected graph $G=(V, E, s, t)$ is minimal, if $G-\{e\}$ for any $e\in E-E(\pi)$ isshown in Fig.1 is a -edge-cut s-t
not -edge-cut s-t 2-edge-connected. For example, the graph$v_{9}(=t)$ .
$v_{0}(=s),$:
where
But it is not minimal
2-edge-connected graph,
as $G-\{e\}$ is -edge-cut s-t 2-edge-connected. Furthermore, the set of all -edge-cut s-t 2-edge. For example, in the graphconnected subgraphs of an s-t pathofis denoted by
given in Fig.1, $W(G, \pi)=\{G-\{e=(u_{1}, u_{2})\}, G-\{(u_{1}, v_{4}), (u_{2}, v_{5}), (v_{3}, v_{5})\}\}$ . Clearly, thefollowing Lemma 4.1 holds.
$G$

$\pi$

$G$

$G$

$\pi$

$\pi$

$G$

$G$

$\pi$

$\pi$

$G$

$\pi$

$\pi$

$v_{1},$ $v_{2},$ $v_{3},$ $v_{4},$ $v_{5},$ $v_{6},$ $v_{7},$$\pi$$v_{8},$

$\pi$

$\pi$

$\pi$

$G$

$\mathcal{W}(G, \pi)$$G$Fig.1 A z-edge-cut s-t 2-edge-connected graph.

Lemma 4.1. If
holds.

$\lambda_{st}(G)\geq 2$

holds and an s-t path

$\pi$

of

$G$

is an s-t edge-cut-path, then$\mathcal{W}(G, \pi)\neq\phi$$\square$Lemma 4.2. In a graph $G=(V, E, s,t)$ , if there exists an s-t paththe following formula holds.
$\lambda_{st}(G-E(\pi))=\lambda_{st}(G)-1$ .

$\pi$satisfying$\mathcal{W}(G, \pi)=\phi$, thenProof. Clearly, $\lambda,t(G-E(\pi))\leq\lambda_{st}(G)-1$ holds. Assume that $\lambda_{st}(G-E(\pi))<\lambda_{st}(G)-1$
holds. By this assumption, there exists a minimum s-t edge-cutset “ in $G-E(\pi)$ that satisfies$|E^{*}|\leq\lambda_{st}(G)-2$
by Menger’s Theorem [4]. Consider graph $G-E^{*}$ , and it is clear that all s-t
is an s-t edge-cut-path of $G-E^{*}$ . Furpaths in $G-E^{*}$ share at least one edge of $E(\pi)$ , i.e.,$E’$$G-E^{*}$. As $E’\cup E$ “ is an s-t edge-cutset of,thermore, letbe a minimum s-t edge-cutset of“$|E’\cup E$ $|=|E’|+|E^{*}|\geq\lambda_{st}(G)$ holds. By$|E^{*}|\leq\lambda_{st}(G)-2$ ,we obtain $|E’|=\lambda_{st}(G-E^{*})\geq 2$ ,holds by Lemma 4.1.
contradicting the fact that
$E$

$\pi$

$G$

$\mathcal{W}(G, \pi)\neq\phi$

We now prove the following Theorem 4.2.

$\square$84
Theorem 4.2. In a graph $G=(V, E, s, t)$ , an s-t path number functionofis exact iff for any
with $P_{st}(G-U)\neq\phi,$ $\mathcal{W}(G-U, \pi_{m(G-U,f)})=\phi$ holds.
is exact and
Proof. Necessity: Assume that an s-t path number function offor somewith $P_{st}(G-U)\neq\phi,$ $\mathcal{W}(G-U, \pi_{m(G-U,f)})\neq\phi$ holds. By $\mathcal{W}(G-U, \pi_{m(G-U,f)})\neq\phi,$ $G-U$ has asubgraph $G’\in \mathcal{W}(G-U, \pi_{m(G-U,f)})$ . $\lambda_{st}(G’)=2$ holds by the definition of $\mathcal{W}(G-U, \pi_{m(G-U,f)})$ .
As $\pi_{m(G-U,\int)}$ is the s-t path with the minimum number of $G’$ and an s-t edge-cut-path of $G’$ , wehave FEDP $(G’)f)=\{\pi_{m(G-U,j)}\}$ by FEDP. Hence, $|FEDP(G’, f)|(=1)<\lambda_{st}(G’)(=2)$ holds,
contradicting the fact that is exact.
Sufficiency: Assume that for any
with $P_{st}(G-U)\neq\phi,$ $\mathcal{W}(G-U, \pi_{m(G-U,f)})=\phi$ holds.
$|FEDP(G-U, f)|=\lambda_{st}(G-U)1_{1}olds$ by
Then it is easy to prove that for any$iteratively\square$
applying Lemma 4.2.
$G$

$f$

$U\subseteq E$

$G$

$f$

$t1_{1}at$$U\subseteq E$$f$$U\subseteq E$$U\subseteq E,$

4.2

A Necessary and Sufficient Condition of s-t Paths

Definition 4.2.(Prohibitive s-t Path Set)Let
be a subset of the set of all s-t paths of . If, for each s-t path-edge-cut s-t 2-edge-connected subgraphin that satisfies
called a prohibitive s-t path set.
$G$

$P(\subseteq P_{st}(G))$$G$$G_{\pi}\in \mathcal{W}(G, \pi)$$\pi$

Procedure TEST
Input: A graph $G=(V, E, s, t)$ .
Output: Either an s-t path number function
BEGIN

$f$

of

$G$

$\pi$

of

$P$

$P_{st}(G_{\pi})\subseteq P$

or a subset$P$, there is a
, then $P$ is$\square$of $P_{st}(G)$ .

$P:=P_{st}(G);i:=1;Q:=\{\pi\in P_{st}(G)|\mathcal{W}(G, \pi)=\phi\}$ ;WHILE $Q\neq\phi$ DO

BEGIN$:=P-Q$ ;REPEAT
Select an s-t path from ;$f(\pi)$ $:=i;i$ $:=i+1;Q$ $:=Q-\{\pi\}$
UNTIL $Q=\phi$ ;$:=$ { $\pi\in P|P_{st}(G_{\pi})\not\subset P$,
for all
END;
IF $P=\phi$ THEN output
ELSE output
END.
$P$

$Q$

$\pi$

$Q$

$G_{\pi}\in \mathcal{W}(G,$$\pi)$

}

$P$

$f$

口

Clearly, the following Lemma 4.3 holds by Definitions 4.1 and 4.2.

Lemma 4.3. If TEST outputs an s-t path number function of , then is exact, when a graph$G=(V, E, s, t)$ is input. If TEST outputs a subset
of $P_{st}(G)$ , then is a prohibitive s-t path set,when a graph $G=(V, E, s,t)$ is input.
$f$

$P$

$G$

$f$

$P$

$\square$If there is a prohibitive s-t path set $P(\subseteq P_{st}(G))$ where $G=(V, E, s, t)$ , then there does not exist
any exact s-t path number function . Otherwise, if has an exact s-t path number function , andsupposebe the s-t path of the minimum number with respect to among . By Definition 4.2,$f$$\pi_{m}$

$G$

$f$

$f$

$P$

85
in that satisfies. Thus,is also the s-t path of the minthere is. Therefore, by FEDP, FEDP $(G_{\pi_{m}}, f)=1<\lambda_{st}(G_{\pi_{n}})=2$
imum number with respect to inholds. This leads to a contradiction that is an exact s-t path number function of . Hence, byTheorem 4.2 and Lemma 4.3, the following Theorem 4.3 holds.
$G_{\pi_{m}}\in \mathcal{W}(G, \pi_{m})$$G$$P_{st}(G_{\pi_{m}})\subseteq P$$f$$\pi_{m}$$G_{\pi_{m}}$

$G$

$f$

Theorem 4.3. In a graph $G=(V, E, s, t),$has an exact s-t path number function iff it contains
口no prohibitive s-t path set as its s-t path subset.
$G$

4.3

Characterization of Graph Having a Prohibitive s-t Path Set

A graph is connected if there is a path connecting each pair of vertices and otherwise disconnected.
A connected component of is a maximal connected subgrapb, which is simply called a component.
$x\neq v$ and $y\neq v$ such that all the paths connecting
If there exist vertices andand have as
an internal vertex, then is an articulation vertex. A two-terminal connected graph is said to be $s,t$
non-sepamble if its subgraph obtained by removing $s,t$ is connected. In the following discussion, we
is an s,t non-separable two-terminal connected graph, unless otherwise specified.
as sume that
$G$

$x$

$x$

$y,$

$y$

$v$

$v$

$G$

Definition 4.3. (s-t 2-edge-connected Articulation Vertex)
A vertex is said to be an s-t 2-edge-connected articulation vertex of , if is an s-t articulation
vertex of andexist both two edge-disjoint s-v paths and two edge-disjoint v-t paths in G.
$G$

$v$

$G$

$v$

$t1_{1}ere$$\square$For example, in the graph illustrated in Fig.2(a), vertices
tion vertices of .

$u,$ $v,$ $w$

are s-t 2-edge-connected articula-

$G$

(a)

(c)

(b)

(d)

Fig.2An illustration of separation ofatan s-t $2- edge\prime connectedani_{Cu}|at\uparrow onve\mathfrak{n}eX$ .
$G$Definition 4.4. (Separation of$G$at an s-t 2-edge-connected Articulation Vertex)

86
Assume that has an s-t 2-edge-connected articulation vertex . The following sequence of operationsat an s-t 2-edge-connected arttculation vertex .
is said to be separation of(i) The two components
are obtained by removing from .
and
(or
).
(ii) is connected to) with all edges $(n, v))s$ of having one end vertex in(or(iii) Note that
contains either of. If contains (or t) then let (or t) be (or ) and let
are similarly defined for.
be (or ).
and
$G$

$v$

$G$

$v$

$C_{2}$$C_{1}$$C_{1}$$v$$t_{1}$$s_{1}$$s_{2}$

$G$

$v$

$G$

$C_{2}$$C_{1}$$v$$s,$$C_{1}$$t$$\iota\ell$

$s$

$s$

$s_{1}$$t_{1}$$\square$$C_{2}$$t_{2}$$C_{2}$$C_{1}$For example, the two graphs illustrated in Fig.2(b),(c) are obtained by separation of the graphgiven in Fig.2(a) at an s-t 2-edge-connected articulation vertex .
$v$

Definition 4.5. (Prohibitive Graph)
A graph is said to be a prohibitive graph, if , or one of the graphs derived from by separations ofat all s-t 2-edge-connected articulation vertices in is homeomorphic to the graph shown in Fig.3.
$G$

$G$

$G$

$G$

$G$

$\square$

The two graphs illustrated in Fig.2(a),(b) are both prohibitive graphs. But the graph given
in Fig.2(d), although it contains a subgraph homeomorphic to the graph sbown in Fig.3, is not aprohibitive graph as the vertex is not its s-t 2-edge-connected articulation vertex and it is not homeomorphic to the grapb shown in Fig.3. It is easy to verify that for a prohibitive graph $G,$ $P_{st}(G)$ is aprohibitive s-t path set. Thus, we immediately obtain the following Lemma 4.4.
$n$Fig.3 A prohibitive graph.

Lemma 4.4. If
contains a prohibitive graph as its subgraph, then it also has a prohibitive s-t path
set as its s-t path subset.
$G$$\square$Now, we show tbat if
has a prohibitive s-t path set as its s-t path subset, then it contains aprohibitive graph as its subgraph. For our aim, we need more definitions.
$G$

Definition 4.6.(Attachment Vertex $[5][6]$ )An attachment vertex of a subgraphinis a vertex ofwith some edge notincident in.
belonging to
Definition 4.7.(Bndges $[5],[6]$ )Let be a fixed subgraph of . A subgraphof is said to be J-detached in if all its attachment
vertices are in . We define aof inas any subgraphthat satisfies the following three
conditions:(i)
is not a subgraph of .
(ii)
is J-detached in .
(iii) No proper subgraph of satisfies both (i) and (ii).
Definition 4.8.(Degenerate and Proper Brtdges. Nucleus of a Bridge $[5],[6]$ )An edge $e=(u, v)$ of
not belonging to but having both end vertices inis referred to as adegenerate bridge.
Letbe the graph derived fromby deleting the vertices of and all edges incident to them.
$G$$G_{1}$$G$$G_{1}$$\square$$G_{1}$

$G$

$J$

$J$

$b_{7\dot{Y}}dge$

$B$

$B$

$G_{1}$

$G$

$J$

$G$

$G$

$B$

$J$

$G$

$B$

$\square$$G$$G^{-}$

$J$

$G$

$J$

$J$

87
be the subgraph of obtained from $C$ by adjoining to it
. Let
Let
be any component ofand adjoining also thehaving one end vertex in $C$ and the other end vertex ineach edge ofsatisfies the conditions (i),(ii),(iii) in Definitionend vertices in of all such edges. The subgraphis the nucleus of B.
4.7 and is a bridge. Such a bridge is called to be proper. The component $C$ of
$C$

$G$

$B$

$G^{-}$

$G$

$J$

$B$

$J$

$G^{-}$$\square$$v_{6}(=t)$ , thenbe an s-t path : $v_{0}(=s))v_{1},$For the graphshown in Fig.4, letproperbridgesare all attachment vertices of in G.
areall vertices onother thanof inis a degenerate bridge of in . By Definitions 4.64.7, the following Lemma 4.5
andobviously holds.
$G$

$J$

$\pi$

$G$

$\pi$

$\pi$

$v_{2},$$B_{1},$$\pi$$v_{4}$$B_{4}$$v_{4},$$v_{5},$$B_{3}$

$G$

$\pi$

$Fig.4$$v_{3},$$B_{2},$

An $i||ustration$ of attachment venices, bridges and $nuc|ei$ .

Lemma 4.5. Let be an s-t path of . If there is a proper bridge of in , then any two vertices
in are connected by a path consisting of edges and vertices only in the nucleus of .
$G$

$\pi$

$B$

$\pi$

$G$

$B$

$B$

$u,$ $v$

Lettobe a path from$v_{j}\rangle$ is a subpath of , and denoted by$\gamma$:$v_{0},$$v_{1},$$\ldots,$$v_{k-1},$ $v_{k}$$v;,$ $v_{i+1}\ldots,$ $v_{j-1},$$v_{k}$$v_{0}$$\gamma$of$G$$\square$. If $0\leq i<j\leq k$ , then the sequence$\gamma[v;, v_{j}]$.

Definition 4.9.(Path Avoiding s-t Path )andLet be an s-t path of . For two vertices $v:,$
in $V(\pi)$ , a path betweenedges not in $E(\pi)$ and vertices not in $V(\pi)$ except $v;,$ is said to be avoiding .
$\pi$

$G$

$\pi$

$v_{i}$$v_{j}$For example, the path$v_{1},$ $u_{1},$$u_{2},$

is avoiding tbe s-t path

$v_{5}$$v_{j}$

consisting of$\square$$\pi$$v_{j}$$\pi$in the graph$G$illustrated in Fig.1.

Definition 4.10. (Order Relation with Respect to an s-t Path )$v_{k}(=t)$ be an s-t path of. We define an order relation
Let : $v_{0}(=s),$
on $V(\pi)$ with$v_{j}(0\leq
i,
j\leq
k),$
;
respect to as follows: For any $v;,$
holds iff $i<j$ holds. If
is said to be to the left (right) of.
)
Definition 4.11.(Intersection Vertex of Two Paths
Let
be two paths of . A vertex is called an intersection vertex of
if and have at.
is denoted byleast three distinct edges incident to . The set of all intersection vertices of
$\pi$

$\pi$

$v_{1},$$\ldots,$$G$$v_{k-1},$$<_{\pi}$$v_{i}<_{T}v_{j},$$v;<_{\pi}v_{j}$$\pi$$v_{j}(v_{i})$$(v_{j})$$\square$$\pi,$$\pi,$$G$$\alpha$$\alpha$

$v$

have

$G$

given in Fig.1, for two s-t paths$V_{\pi\alpha}=\{v_{1}, v_{6}, v_{7}, v_{9}\}$.

Definition 4.12.(Interlacing Subpaths)$\alpha$$\pi,$$v$

In the graph$v$$\pi,$$\pi$

and$\alpha$: $v_{0}(=s),$$v_{1},$$\pi$$u_{1},$$u_{2},$$\alpha$$V_{\pi\alpha}$$\alpha$$v_{6},$$v_{7},$$v_{9}(=t)$$\square$

, we

88
Let
be twoLetbe the set of all intersection. Letedge-disjoint s-t paths ofbe the set of all, where $x_{1}<_{\pi}x_{2}<_{\pi}\cdots<_{\pi}x_{p}$ . Let
vertices ofbe the set, where $y_{1}<_{\pi}y_{2}<_{T}\cdots<_{\pi}y_{q}$ . Let
intersection vertices ofof ahave in common, where $z_{1}<_{\pi}z_{2}<_{T}\cdots<_{\pi}z_{r}$ . Subpathsof all vertices which, are said to be interlacingof avoiding , where either $x;<_{\pi}y_{i}$ oravoiding and.
when
subpaths, if the subpath $\pi[x;, y_{i+1}](\pi[y_{i,:+1}x])$ contains no vertex of
Suppose that$G$

$G_{T}\in \mathcal{W}(G, \pi)$( t) satisfying: $v_{0}(=s),$
has an s-t path
be a minimal -edge-cut s-t 2-edge-connected subgraph of .
$\pi$$v_{1},$$\mathcal{W}(G, \pi)\neq\phi$$=$.

$\alpha,\beta$$V_{\pi\alpha}=\{x_{1}, x_{2}, \ldots, x_{p}\}(\subseteq V(\pi))$$V_{\pi\beta}=\{y_{1}, y_{2}, \ldots, y_{q}\}(\subseteq V(\pi))$$\alpha$$\pi,$$\alpha,$$V_{\pi\alpha\beta}=\{z_{1}, \ldots, z_{r}\}(\subseteq V(\pi))$$\beta$$\pi,$$\alpha[x_{i,:+1}x]$$\beta$$\beta[y_{j}, y_{j+1}]$$\pi$$v_{k-1},$ $v_{k}$$G$$G_{\pi}$$\pi,$$\ldots,$

$\pi$

$\pi$

$\beta$$y_{j}<_{\pi}x_{i}$$x_{i}<_{\pi}y_{j}(y_{j}<_{\pi}.

$V_{\pi\alpha\beta}$

x_{i})$$\square$given in Fig.1, for two edge-disjoint s-t paths;$v_{9}(=t),$ $\beta:v_{0}(=s),$ $w,$ $vv\iota$),: $v_{0}(=s),$$vc$. And subpaths
we havepaths.
arealso
interlacing
subpaths,andandinterlacing
are
and
.
are onare not interlacing subpaths as
andBut$P(\subseteq
P_{st}(G))$,
thenmust contain
path
a
s-t
set
prohibitive
In order to show that if graph has
a prohibitive graph as its subgraph, we can prove the following Lemma 4.6 and Lemma 4.7.
In the graph$\alpha$$v_{1},$$G$$u_{1},$ $v_{4},$ $v_{5},$ $u_{2},$ $v_{6},$$V_{\pi\beta}=\{v_{0}, v_{2}, v_{3}, v_{5}, v_{6}, v_{8}\},$$\beta[v_{6}, v_{8}]$$\alpha[v_{1}, v_{4}]$$t$$V_{\pi\alpha\beta}=\{\iota_{0}, \iota_{5)}v_{6}, v_{9}\}$$\beta[1)6, v_{8}]$$\alpha[v_{7}, v_{9}]$$\beta[v_{0}, v_{2}]$$\alpha[v_{1}, v_{4}]$))$v_{7},$$V_{\pi\alpha}=\{v_{1}, v_{4}, v_{5}, v_{6}, v_{7}, v_{9}\},$$\pi[v_{0}, v_{8}]$$v_{5)}v_{6}\in V_{\pi\alpha\beta}$

$G$

$G$

has a prohibitive s-t path set . Then there is an s-t path ofLemma 4.6. Suppose thatof andofincontains two interlacing subpaths
whose proper bridge, whereis a minimal -edge-cut s-t 2-edge-connected subgraph of , andwith respect to in.
are two edge-disjoint s-t paths in
Sketch of Proof. Let be a prohibitive s-t path set of . We can find the s-t path of satisfying
the following condition by using the following procedure .
Condition : There is a proper bridge of in suth that contains interlacing subpaths $\alpha[x, x]$, whereof with respect to in
is a minimal -edge-cut s-t 2-edgeof and.
connected subgraph of , andare two edge-disjoint s-t paths in: Let be an s-t path of . Let be a proper bridge of in . We do the following Loop
Proceduiteratively.
of such that there
Loop: If satisfies Condition then end. Otherwise, we can find an s-t patl]
is a bridge $B’$ of inwhose nucleus contains the nuleus of and there are more vertices in the
nucleus of $B’$ than in the nucleus of . Let $B,$ be $B’,$ , respectively.
Note that, in each loop, the nucleus of increases at least by one vertex. Thus tbe loop will end
in at most $|V|$ times, where is the set of vertices in .
$P$

$G$

$B$

$\pi$

$\alpha[x_{i}, x_{i+1}]$$G_{\pi}$$G_{\pi}$$\pi$$\alpha,$$G$$\beta[y_{j}, y_{j+1}]$$\alpha$$P$$\beta$

$G$

$\pi$

$G_{\pi}$$\beta$

$G$

$P$

$I$

$B$

$I$

$\beta[y_{j}, y_{j+1}]$$\alpha$$\beta$$\alpha,$$G_{\pi}$$G_{\pi}$$\pi$$G_{\pi}$$\beta$

$P$

$\pi$

$B$

$\pi$

$G$

$\pi’$$I$$\pi$$\pi’$

$P$

$B$

$G$

$\pi$

$\pi$

$G$

$\tau \mathfrak{r}I$

$\pi$

$I$

$P$

$B$

$G$

$B$

$\pi’$

$\pi$

$B$

$G$

$V$

$\square$Fig.5 An illustration of the proof of Lemma 4.7.

Lemma 4.7. Suppose that has an s-t path. Let
s-t paths of$G$$G_{\pi}\in \mathcal{W}(G, \pi)$$\pi$satisfying$V_{\pi\alpha}=\{x_{1}, x_{2}, \ldots, x_{p}\},$$\mathcal{W}(G, \pi)\neq\phi$. Let

be two edge-disjoint
and$\alpha,$$V_{\pi\beta}=\{y_{1}, y_{2}, \ldots, y_{q}\}$$\beta$$V_{\pi\alpha\beta}=\{z_{1}, \ldots, z_{r}\}$89
ofbe defined as in Definition 4.12. If a bridge of in contains interlacing subpaths$t1_{1}enG$ contains a prohibitive graph as its subgraph.
of inwith respect toandSketch of Proof. By the known conditions given in this lemma, we construct a prohibitive graph as
its subgraph.
between an internal vertex on $\alpha[x:, x:+1]$ and an internal
By Lemma 4.5, there is a pathconsisting of edges and vertices only in the nucleus of bridge , i.e.,isvertex on
except. See Fig.5. Thus, we can also find a prohibitive graph asvertex-disjoint path withis traced.
subgraph of independently of the way how the path$B$$\beta[y_{j}, y_{j+1}]$$G_{\pi}$$\beta$

$\pi$

$G$

$\alpha[x_{i}, x_{i+1}]$$\pi,$$u$$\pi_{uv}$$v$$\alpha$$B$$\beta[y_{i}, y_{i+1}]$$\pi$$\pi_{uv}$$u,$ $v$$G$$\square$$\pi_{uv}$

By Theorem 4.3 and Lemmas 4.5, 4.6, 4.7, the following Theorem 4.4 holds.

Theorem 4.4. In a probabilistic graph $(G,p),$graph as its subgraph.

5$\underline{\Gamma}_{(G,f)p)}=\Gamma_{(G,p)}$holds iff$G$contains no prohibitive$\square$

A Method of Computing the Lower Boundof , we show a method of computing
Given a probabilistic graph $(G,p)$ and an s-t path number. We first wish to recall the procedure FEDP and the definition of
the lower boundin section 3.
.
For a probabilistic graph $(G=(V, E, s,t),p)$ and an s-t path number functionof , letdenote the set of all
for which s-t pathis selected as a member of edge-disjoint s-t paths
FEDP $(G-U, f)$ . Let
be the probability of the eventthat all edges ofare failed andall edges of $E-U$ are operative, andis the probability of the event that at least one event, arises in $(G,p)$ . Thus, we have
, for all$G$$f$$\underline{\Gamma}_{(G,j,p)}$$\underline{\Gamma}_{(G,j,p)}$

$G$

$f$

$U\subseteq E$$\mathcal{U}_{j,\pi_{*}}$$\pi_{\mathfrak{i}}$$p(\mathcal{E}_{U})$$\mathcal{E}_{U}$$U$$p(\mathcal{E}_{j,\pi_{i}})$$\mathcal{E}_{U}$$U\in \mathcal{U}_{f,\pi_{i}}$$\underline{\Gamma}_{(G,f,p)}$$=$$\sum_{U\subseteq E}|FEDP(G-U, f)|\rho(G-U)$$\sum^{|P_{t}(G)|}$$\sum$$=$$i=1$$\rho(G-U)$$u\epsilon u_{J,.:}$$\sum^{|P_{2}(G)|}$$\sum$

$=$

$i=1$

$=$

We can compute the lower bound6$U\in ll_{J\cdot:}$$\sum_{1=1}^{|P_{\ell}(G)|}p(\mathcal{E}_{f,\pi:})$$\underline{\Gamma}_{(G,f,p)}$$p(\mathcal{E}_{U})$.

(5)by formula (5) instead of formula (3).

Concluding Remarks

For a probabilistic graph, we proposed a lower bound for estimating the expected maximum number ofedge-disjoint s-t paths. The necessary and sufficient conditions with respect to both s-t path number
function and graph construction, where this lower bound coincides with the expected maximum numberof edge-disjoint s-t paths, are clarified. A method of computing this lower bound is also given, althoughby this computing method the lower bound does not seem to be efficiently computed for a generalprobabilistic graph.

90
However, for a probabilistic one-layered s-t graph, (a two-terminal graph where the subgraph obis exactly a simple path. Fig.6 illustrates an example of one-layered s-t
tained by deleting its
graph.) as it satisfies the necessary and sufficient conditions and the number of all its s-t paths is apolynomial function in the number of its vertices, the lower bound based on its exact s-t path number
function can efficiently be computed by the computing method sbown in section 5, i.e., the expected
maximum number of edge-disjoint s-t paths in a probabilistic one-layered s-t graph can efficiently be
computed. Detailed description of these proofs is lengthy and to be reported elsewhere.
$s,$

$t$

Fig.6 A one-layered s-t graph.

References[1] M. O. Ball: “Computational complexity of network reliability analysis: An overview”, IEEE Trans.
Reliability, Vol.R-35, pp230-239 (1986).
[2]

P. Cheng and S. Masuyama: Problem of computing the expected maximum number of vertexdisjoint s-t paths on probabilistic graphs”, Research Report $COA\prime fP92- 1$ , Inst. Electron. Infor.
Comm. $Eng$ . Japan, pp1-8, (1992) (in Japanese).
([3] C. J. Colbourn: The Combinatorics of Network Reliabtlity, Oxford University Press (1987).
[4] K. Menger:“ Zer allgemeinen kurventheorie”, Fund. Math. $Vol10,$ $pp.96- 115(1927)$ .
[5] B. Mishra and R. E. Tarjan: “ A linear-time algorithm for finding a ambitus“, Algorithmica, 7,
pp.521-554(1992).
[6]

W. T. Tutte: “ Bridges and hamiltonian circuits in planar graph”, Aequationes mathematicae,
15, pp.1-13(1977).