# On the 2-MRS Problem in a Tree with Unreliable Edges

Authors: Wei Ding; Yu Zhou; Guangting Chen; Hongfa Wang; Guangming Wang
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

This paper extends the well-known most reliable source (1-MRS) problem in unreliable graphs to the 2-most reliable source (2-MRS) problem. Two kinds of reachable probability models of node pair in unreliable graphs are considered, that is, the superior probability and united probability. The 2-MRS problem aims to find a node pair in the graph from which the expected number of reachable nodes or the minimum reachability is maximized. It has many important applications in large-scale unreliable computer or communication networks. The #P-hardness of the 2-MRS problem in general graphs follows directly from that of the 1-MRS problem. This paper deals with four models of the 2-MRS problem in unreliable trees where every edge has an independent working probability and devises a cubic-time and quadratic-space dynamic programming algorithm, respectively, for each model.


---

## Body

## 1. Introduction

A computer network or communication network is commonly denoted by an undirected graphG=(V,E), where V is the node set, each of which represents a processing or switching element, and E is the edge set, each of which represents a communication link [1, 2]. Given any two different nodes u and v, the communication between u and v is achieved by a u-to-v path. Network failures may frequently happen to links or nodes [3, 4]. Such a network is called unreliable or probabilistic. In the past decade, a large number of network reliability problems have been extensively studied [5–20]. Many of them can be reduced to the problem of finding an optimal location for placing a server in an unreliable network [7–12, 14, 15, 17–20]. In addition, the most reliable route problem has been studied in [9, 14, 19] and its delay-constrained version has been studied in [21]. Recently, the problem of placing servers [22] and the problem of assigning links [23] in probabilistic wireless networks have been considered. Also, the continuous data collection schemes have been proposed in probabilistic wireless sensor networks (WSNs) [24, 25].Given an unreliable graphG with n nodes and m edges, we call v a reachable node of u (or call v reachable from u) if u can reach v correctly. The probability of successful communication from u to v is called the reachable probability of u to v. The sum reachability of a node refers to the expected number of reachable nodes from it. The node with a maximum sum reachability is called a sum-max most reliable source (Sum-Max 1-MRS) of the graph. The Sum-Max 1-MRS problem has caused a lot of researchers’ interests; see [7–12, 14, 15, 17, 20]. The minimum reachability of a node refers to its minimum reachable probability to another node. The node maximizing its minimum reachability is called a min-max most reliable source (Min-Max 1-MRS) of the graph. The Min-Max 1-MRS problem has been studied in [9, 20]. The Sum-Max 1-MRS and Min-Max 1-MRS are collectively called a 1-MRS for short. In addition, we refer readers to [18, 19] for the 1-center problem in unreliable graphs and related algorithms. Obviously, both 1-MRS and 1-center problems are a good location for placing a server in unreliable graphs.It is well known that the 1-MRS problem and 1-center problem are both #P-hard in general graphs [3, 4, 18]. However, they are tractable under the most reliable route policy. Helander and Melachrinoudis presented a polynomial time algorithm [14], and Ding gave an O(mn+n2logn)-time algorithm [9] for the 1-MRS problem. Santiváñez et al. designed a polynomial time algorithm for the 1-center problem [19]. Moreover, both the 1-MRS problem and 1-center problem are also tractable in several types of sparse networks. For tree graphs with unreliable edges, Melachrinoudis and Helander designed a quadratic time algorithm [15], and Xue designed a linear time algorithm for the 1-MRS problem [20]. Santivanez and Melachrinoudis gave a linear time algorithm for the 1-center problem [18]. Ding and Xue considered the 1-MRS problem in the tree graphs with unreliable nodes and devised a linear time algorithm using the complementary dynamic programming method [10]. For ring graphs, Ding gave a quadratic time algorithm [8]. For ring-tree graphs, Ding and Xue considered an underlying topology of a strip, presented a polynomial time divide-and-conquer algorithm [11], considered an underlying topology of a tree, and presented a fast parallel algorithm based on the complementary dynamic programming [12]. For series-parallel graphs, Colbourn and Xue devised a linear time dynamic programming algorithm [7].As networks grow rapidly in size, they become increasingly vulnerable to failures. Therefore, a single server can no longer satisfy the requirement of service from the whole network. In this scenario, we suggest to place at least two servers on unreliable networks with a large size. The rest of the paper focuses on the case of placing two servers and extends the 1-MRS problem to the 2-MRS problem, includingsum-max 2-most reliable source (Sum-Max 2-MRS) and min-max 2-most reliable source (Min-Max 2-MRS). Given any a node pair 〈u,v〉, the probability of u and v reaching another node w successfully is called the reachable probability of 〈u,v〉 to w. The paper considers two types of reachable probability models of node pair, that is, the superior probability and united probability, formally defined in Section 2.2. Under both probability models, a cubic-time and quadratic-space algorithm is presented, respectively, for finding a Sum-Max 2-MRS and a Min-Max 2-MRS on trees with unreliable edges. Note that this paper is the first one to propose and study the 2-MRS problem.The remainder of this paper is organized as follows. In Section2, we define notations and the 2-MRS problem formally and show several fundamental lemmas. We present a cubic-time algorithm, respectively, for the Sum-Max 2-MRS problem in Section 3 and the Min-Max 2-MRS problem in Section 4 on tree graphs with unreliable edges. In Section 5, we give an example for illustrating our algorithms. In Section 6, we conclude the paper with some future research topics.


## 2. Preliminaries

### 2.1. Notations

Let𝒢=(𝒱,ℰ,p) be an undirected connected graph, where 𝒱 is the node set, ℰ is the edge set, and each edge e∈ℰ has a weight p(e) representing the working probability on e. Suppose that all edges have an independent working probability and all nodes are immune to failures. Let 〈u,v〉 be a node pair of 𝒢. We use π(u,v) to denote a simple path in 𝒢 connecting u and v and also use π(u,v) to denote the event that π(u,v) works correctly for simplicity of presentation. Let Pr(π(u,v)) denote the probability of π(u,v) working correctly and Pr(u,v) the probability of u reaching v among 𝒢. Specifically, Pr(π(u,v))=p(e)=p(u,v) when π(u,v) is just an edge e={u,v} in 𝒢. Note that π(u,v) works correctly if and only if all edges of π(u,v) work correctly simultaneously. Let 𝒱(π(u,v)) and ℰ(π(u,v)) denote the set of nodes and edges on π(u,v), respectively. So,
(1)Pr(π(u,v))=∏e∈ℰ(π(u,v))‍p(e).LetT=(V,E,p) be an undirected tree graph, where V is the node set, E is the edge set, and every edge e∈E has a probability weight p(e) as defined above. For any 〈u,v〉 of T, there exists a unique path π(u,v) in T connecting u and v. Thus, it always holds that Pr(u,v)=Pr(π(u,v)) in T. Let Pr(u,u)=1 when u=v. An unrooted tree can be transformed into a rooted tree by designating any node as the root. Without any loss of generality, we pick out any node u∈V and transform T into a tree rooted at u, denoted by Tu=(Vu,Eu,p). Clearly, Vu=V and Eu=E. For any v∈Vu, we use Cu(v) to denote the set of the children of v in Tu and Tu(v) to denote the subtree of Tu rooted at v. Let Vuα(v) denote the set of nodes in Tu(v) and Vuβ(v) the set of nodes outside Tu(v). Specifically, Cu(v)=∅ and Vuα(v)={v} when v is a leaf of Tu. For any v∈Vu, we use fu(v) to denote the parent of v in Tu and 𝒬u(v) to denote the set of ancestors of v in Tu. Specifically, 𝒬u(v)={u} when v∈Cu(u) and 𝒬u(u)=∅. For any w∈𝒬u(v), we use suv(w) to denote the child of w on π(u,v) in Tu. Let Cuv(w) denote the set of children of w in Tu other than suv(w); that is, Cuv(w)=Cu(w)∖{suv(w)}. Let Hu=maxv∈Vu|𝒬u(v)|. Suppose that u is located at the 0th level in Tu. So, Tu has Hu+1 levels in total. Let Vu(h), h=0,1,2,…,Hu, denote the set of nodes on the h-level of Tu. Also, we use D (resp., Du) to denote the set of leaves of T (resp., Tu). Clearly, |Du| is equal to |D|-1 if u is a leaf of T and |D| if u is not a leaf.


### 2.2. Problem Statements

Given any〈ui,uj〉 of 𝒢 and any v∈𝒱, the maximum in the reachable probability of ui to v and that of uj to v is called the superior probability of 〈ui,uj〉 to v, denoted by ℱ1(ui,uj;v). The probability of ui to v,uj to v, or both is called the united probability of 〈ui,uj〉 to v, denoted by ℱ2(ui,uj;v). The superior probability and united probability are collectively called the reachable probability of node pair.Problem 1.
Given an undirected connected network𝒢=(𝒱,ℰ,p), where every edge e∈ℰ has a weight representing the working probability p(e) on e, the objective is to find a node pair in 𝒢 such that the sum reachability (resp., minimum reachability) of the node pair is maximized.Thesum reachability of 〈ui,uj〉 is referred to as the expected number of reachable nodes in 𝒢 from 〈ui,uj〉, denoted by 𝔼λ[ui,uj]. The optimal solution of Problem 1 with the objective of maximizing the sum reachability of node pair is called Sum-Max 2-MRS of 𝒢, denoted by 〈ui*,uj*〉. We have
(2)𝔼λ[ui,uj]=∑v∈𝒱‍ℱλ(ui,uj;v),λ=1,2,(3)𝔼λ[ui*,uj*]=maxui,uj∈𝒱,ui≠uj𝔼λ[ui,uj].Theminimum reachability of 〈ui,uj〉 is referred to as the minimum reachable probability of 〈ui,uj〉, denoted by 𝕄λ[ui,uj]. The optimal solution of Problem 1 with the aim of maximizing the minimum reachability of node pair is called Min-Max 2-MRSof 𝒢, denoted by 〈ui⋆,uj⋆〉. We have
(4)𝕄λ[ui,uj]=minv∈𝒱ℱλ(ui,uj;v),λ=1,2,(5)𝕄λ[ui⋆,uj⋆]=maxui,uj∈𝒱,ui≠uj𝕄λ[ui,uj].The Sum-Max 2-MRS problem and Min-Max 2-MRS problem are collectively called the2-MRS problem. Based on the #P-hardness of the 1-MRS problem in general graphs [3, 4], we conclude that the 2-MRS problem in general graphs is also #P-hard. However the 1-MRS problem in tree graphs is tractable [10, 15, 20]. In the remainder of this paper, we will deal with the 2-MRS problem in tree graphs. All the notations and their explanations used in the paper are listed in Table 2.


### 2.3. Fundamental Lemmas

LetA⊕B denote the union of two disjoint sets A and B. Lemma 2 shows the decomposition scheme at uj of Vui for any 〈ui,uj〉 of T, see Figure 1. The proof is straightforward and omitted here.Illustration of the decomposition ofTui for any ui∈V.
(a)
Decomposition ofTui
(b)
Decomposition ofVuiα(uj)
(c)
Decomposition ofVuiβ(uj)Lemma 2.
Given any〈ui,uj〉 of T, one has
(6)Vui=Vuiα(uj)⊕Vuiβ(uj),
in which
(7)Vuiα(uj)=(⨁s∈Cui(uj)Vuiα(s))⊕{uj},(8)Vuiβ(uj)=(⨁w∈𝒬ui(uj)⨁s∈Cuiuj(w)Vuiα(s))⊕𝒬ui(uj).Lemma 3.
Given any treeTu=(Vu,Eu) rooted at u, one has,
(9)∑v∈Vu‍|𝒬u(v)|≤12|Vu|(|Vu|-1).Proof.
LetTu=(Vu,Eu) be a tree rooted at u with an arbitrary topology and TuΔ=(VuΔ,EuΔ) a line with the same number of nodes as Tu. First, we prove that ∑v∈Vu‍|𝒬u(v)|≤∑v∈VuΔ‍|𝒬uΔ(v)|. In fact, Tu can always be derived from TuΔ in the following way. Let L denote the current line and set L=TuΔ initially. We take away the lowest node of L and attach it to another node one by one. Every time we take away the lowest node of L, we set the rest of L to the current line. So, we are sure to obtain a series of trees rooted at u. Suppose that we get m trees, Tu1,Tu2,…,Tum in order. Let Tu0=TuΔ and ak=∑v∈Vu‍|𝒬uk(v)|, k=0,1,…,m. Given any 0≤k≤m-1, Tuk+1 is derived from Tuk by moving the lowest node v′ of L in Tuk. The new level in Tuk+1 at which v′ is located is lower than the previous level in Tuk. So, ak+1≤ak. Therefore, a0≥a1≥⋯≥am. Note that HuΔ=|VuΔ|-1 and |VuΔ(h)|=1, h=0,1,…,HuΔ. We have
(10)a0=∑v∈VuΔ|𝒬uΔ(v)|=∑h=1|VuΔ|-1h=12|VuΔ|(|VuΔ|-1).
Therefore, ∑v∈Vu‍|𝒬u(v)|≤(1/2)|Vu|(|Vu|-1) for any Tu.Lemma 4.
Given any treeTu=(Vu,Eu) rooted at u, one has,
(11)∑v∈Vu|Cu(v)|=|Vu|-1,(12)(|Vu|-1)2|Vu∖Du|≤∑v∈Vu|Cu(v)|2≤(|Vu|-1)2.Proof.
It follows directly fromCu(v)=∅, for all v∈Du and |Eu|=|Vu|-1, that ∑v∈Vu‍|Cu(v)|=∑v∈Vu∖Du‍|Cu(v)|=|Eu|=|Vu|-1.
On one hand,(13)∑v∈Vu|Cu(v)|2=∑v∈Vu∖Du|Cu(v)|2≥(∑v∈Vu∖Du|Cu(v)|)2|Vu∖Du|=(|Vu|-1)2|Vu∖Du|,
where the equality holds if and only if all |Cu(v)|, v∈Vu∖Du, are equal. Let Tu∘=(Vu∘,Eu∘) be a star rooted at u, say, a special case of Tu. On the other hand, we prove that ∑v∈Vu‍|Cu(v)|2≤∑v∈Vu∘‍|Cu∘(v)|2 for any Tu. Let m=|Vu∖Du| and n=|Vu|-1. We label all the nodes in Vu∖{u} by numbers 1,2,…,n. Let xk=|Cu(vk)|, k=1,…,m. Then we build the following restricted optimization problem:
(14)max∑k=1m‍xk2,s.t.∑k=1m‍xk=n,xk≥0,xk∈ℤ,k=1,…,m.
Without loss of generality, we suppose that max{x1,x2,…,xm}=xm. By taking xm=n-∑k=1m-1‍xk into the above objective function, we obtain a new unrestricted optimization problem
(15)maxxk≥0,xk∈ℤf(x1,…,xm-1)=∑k=1m-1‍xk2+(n-∑k=1m-1‍xk)2.
We conclude that, for every k=1,…,m-1,
(16)∂f∂xk=2xk-2(n-∑k=1m-1‍xk)=2(xk-xm)≤0.
Thus, fmax(x1,…,xm-1)=f(0,…,0)=n2 and xm=n. This implies that ∑v∈Vu‍|Cu(v)|2≤(|Vu|-1)2 and the tree rooted at u satisfying the equality is just Tu∘.Lemma 5.
Given any〈ui,uj〉 of T, one has
(17)Pr(ui,uj)=Pr(ui,v)Pr(v,uj),∀v∈V(π(ui,uj)).Proof.
First of all, for any two edge-disjoint pathsπ1 and π2 on T, we prove that π1 and π2 are independent. Suppose that π1 contains edges e1,e2,…,ek1 and π2 contains edges e1′,e2′,…,ek2′. It is obvious that {e1,e2,…,ek1}∩{e1′,e2′,…,ek2′}=∅. Since all of edges e∈E are independent, we conclude that
(18)Pr(π1π2)=∏i1=1k1‍Pr(ei1)∏i2=1k2‍Pr(ei2′)=Pr(π1)Pr(π2).
For any v∈V(π(ui,uj)), π(ui,uj) comprises two edge-disjoint subpaths π(ui,v) and π(v,uj). Therefore, Pr(ui,uj)=Pr(ui,v)Pr(v,uj).Lemma 6.
Given any〈ui,uj〉 of  T and v∈Vui,(i)
ifv∈𝒬ui(uj), then
(19)ℱ1(ui,uj;v)=max{Pr(ui,v),Pr(uj,v)},(20)ℱ2(ui,uj;v)=Pr(ui,v)+Pr(uj,v)-Pr(ui,v)Pr(uj,v),(ii)
ifv∈Vuiα(uj), then
(21)ℱλ(ui,uj;v)=Pr(uj,v),λ=1,2,(iii)
ifv∈Vuiα(s), where s∈Cuiuj(w) and w∈𝒬ui(uj), then
(22)ℱλ(ui,uj;v)=ℱλ(ui,uj;w)p(w,s)Pr(s,v),λ=1,2.Proof.
(i) Whenv∈𝒬ui(uj), it follows directly from the definition of ℱ1(ui,uj;v) that ℱ1(ui,uj;v)=max{Pr(ui,v),Pr(uj,v)}. We see that π(ui,uj) can be partitioned at v into two edge-disjoint subpaths π(ui,v) and π(uj,v). Lemma 5 implies that π(ui,v) and π(uj,v) are independent. The definition of ℱ2(ui,uj;v) means that the value of ℱ2(ui,uj;v) is equal to the probability of π(ui,v)∪π(uj,v). So,
(23)ℱ2(ui,uj;v)=Pr(π(ui,v)∪π(uj,v))=Pr(π(ui,v))+Pr(π(uj,v))-Pr(π(ui,v)∩π(uj,v))=Pr(ui,v)+Pr(uj,v)-Pr(ui,v)Pr(uj,v).
(ii) Whenv∈Vuiα(uj), π(ui,v) is composed of two edge-disjoint subpaths π(ui,uj) and π(uj,v). It follows from Lemma 5 that Pr(ui,v)=Pr(ui,uj)Pr(uj,v). So,
(24)ℱ1(ui,uj;v)=max{Pr(ui,uj),1}Pr(uj,v)=Pr(uj,v).
We see that π(ui,v) works correctly if and only if π(ui,uj) and π(uj,v) work correctly simultaneously. So, π(ui,v)=π(ui,uj)∩π(uj,v). Thus,
(25)ℱ2(ui,uj;v)=Pr((π(ui,uj)∩π(uj,v))∪π(uj,v))=Pr(uj,v).
(iii) Whenv∈Vuiα(s), where s∈Cuiuj(w) and w∈𝒬ui(uj), we observe that π(uk,v), k=i,j, consists of two edge-disjoint subpaths π(uk,w) and π(w,v). Also, π(w,v) comprises two edge-disjoint subpaths π(w,s) and π(s,v) as well. We derive that Pr(uk,v)=Pr(uk,w)p(w,s)Pr(s,v) from Lemma 5. So,
(26)ℱ1(ui,uj;v)=max{Pr(ui,v),Pr(uj,v)}=max{Pr(ui,w),Pr(uj,w)}p(w,s)Pr(s,v)=ℱ1(ui,uj;w)p(w,s)Pr(s,v).
We see thatπ(uk,v), k=i,j, works correctly if and only if π(uk,w) and π(w,v) work correctly simultaneously. So, π(uk,v)=π(uk,w)∩π(w,v). Thus,
(27)ℱ2(ui,uj;v)=Pr((π(ui,w)∩π(w,v))∪(π(uj,w)∩π(w,v)))=Pr(π(ui,w)∩π(w,v))+Pr(π(uj,w)∩π(w,v))-Pr((π(ui,w)∩π(w,v))∩(π(uj,w)∩π(w,v)))=Pr(ui,w)Pr(w,v)+Pr(uj,w)Pr(w,v)-Pr(ui,w)Pr(uj,w)Pr(w,v)=ℱ2(ui,uj;w)p(w,u)Pr(u,v).


## 2.1. Notations

Let𝒢=(𝒱,ℰ,p) be an undirected connected graph, where 𝒱 is the node set, ℰ is the edge set, and each edge e∈ℰ has a weight p(e) representing the working probability on e. Suppose that all edges have an independent working probability and all nodes are immune to failures. Let 〈u,v〉 be a node pair of 𝒢. We use π(u,v) to denote a simple path in 𝒢 connecting u and v and also use π(u,v) to denote the event that π(u,v) works correctly for simplicity of presentation. Let Pr(π(u,v)) denote the probability of π(u,v) working correctly and Pr(u,v) the probability of u reaching v among 𝒢. Specifically, Pr(π(u,v))=p(e)=p(u,v) when π(u,v) is just an edge e={u,v} in 𝒢. Note that π(u,v) works correctly if and only if all edges of π(u,v) work correctly simultaneously. Let 𝒱(π(u,v)) and ℰ(π(u,v)) denote the set of nodes and edges on π(u,v), respectively. So,
(1)Pr(π(u,v))=∏e∈ℰ(π(u,v))‍p(e).LetT=(V,E,p) be an undirected tree graph, where V is the node set, E is the edge set, and every edge e∈E has a probability weight p(e) as defined above. For any 〈u,v〉 of T, there exists a unique path π(u,v) in T connecting u and v. Thus, it always holds that Pr(u,v)=Pr(π(u,v)) in T. Let Pr(u,u)=1 when u=v. An unrooted tree can be transformed into a rooted tree by designating any node as the root. Without any loss of generality, we pick out any node u∈V and transform T into a tree rooted at u, denoted by Tu=(Vu,Eu,p). Clearly, Vu=V and Eu=E. For any v∈Vu, we use Cu(v) to denote the set of the children of v in Tu and Tu(v) to denote the subtree of Tu rooted at v. Let Vuα(v) denote the set of nodes in Tu(v) and Vuβ(v) the set of nodes outside Tu(v). Specifically, Cu(v)=∅ and Vuα(v)={v} when v is a leaf of Tu. For any v∈Vu, we use fu(v) to denote the parent of v in Tu and 𝒬u(v) to denote the set of ancestors of v in Tu. Specifically, 𝒬u(v)={u} when v∈Cu(u) and 𝒬u(u)=∅. For any w∈𝒬u(v), we use suv(w) to denote the child of w on π(u,v) in Tu. Let Cuv(w) denote the set of children of w in Tu other than suv(w); that is, Cuv(w)=Cu(w)∖{suv(w)}. Let Hu=maxv∈Vu|𝒬u(v)|. Suppose that u is located at the 0th level in Tu. So, Tu has Hu+1 levels in total. Let Vu(h), h=0,1,2,…,Hu, denote the set of nodes on the h-level of Tu. Also, we use D (resp., Du) to denote the set of leaves of T (resp., Tu). Clearly, |Du| is equal to |D|-1 if u is a leaf of T and |D| if u is not a leaf.


## 2.2. Problem Statements

Given any〈ui,uj〉 of 𝒢 and any v∈𝒱, the maximum in the reachable probability of ui to v and that of uj to v is called the superior probability of 〈ui,uj〉 to v, denoted by ℱ1(ui,uj;v). The probability of ui to v,uj to v, or both is called the united probability of 〈ui,uj〉 to v, denoted by ℱ2(ui,uj;v). The superior probability and united probability are collectively called the reachable probability of node pair.Problem 1.
Given an undirected connected network𝒢=(𝒱,ℰ,p), where every edge e∈ℰ has a weight representing the working probability p(e) on e, the objective is to find a node pair in 𝒢 such that the sum reachability (resp., minimum reachability) of the node pair is maximized.Thesum reachability of 〈ui,uj〉 is referred to as the expected number of reachable nodes in 𝒢 from 〈ui,uj〉, denoted by 𝔼λ[ui,uj]. The optimal solution of Problem 1 with the objective of maximizing the sum reachability of node pair is called Sum-Max 2-MRS of 𝒢, denoted by 〈ui*,uj*〉. We have
(2)𝔼λ[ui,uj]=∑v∈𝒱‍ℱλ(ui,uj;v),λ=1,2,(3)𝔼λ[ui*,uj*]=maxui,uj∈𝒱,ui≠uj𝔼λ[ui,uj].Theminimum reachability of 〈ui,uj〉 is referred to as the minimum reachable probability of 〈ui,uj〉, denoted by 𝕄λ[ui,uj]. The optimal solution of Problem 1 with the aim of maximizing the minimum reachability of node pair is called Min-Max 2-MRSof 𝒢, denoted by 〈ui⋆,uj⋆〉. We have
(4)𝕄λ[ui,uj]=minv∈𝒱ℱλ(ui,uj;v),λ=1,2,(5)𝕄λ[ui⋆,uj⋆]=maxui,uj∈𝒱,ui≠uj𝕄λ[ui,uj].The Sum-Max 2-MRS problem and Min-Max 2-MRS problem are collectively called the2-MRS problem. Based on the #P-hardness of the 1-MRS problem in general graphs [3, 4], we conclude that the 2-MRS problem in general graphs is also #P-hard. However the 1-MRS problem in tree graphs is tractable [10, 15, 20]. In the remainder of this paper, we will deal with the 2-MRS problem in tree graphs. All the notations and their explanations used in the paper are listed in Table 2.


## 2.3. Fundamental Lemmas

LetA⊕B denote the union of two disjoint sets A and B. Lemma 2 shows the decomposition scheme at uj of Vui for any 〈ui,uj〉 of T, see Figure 1. The proof is straightforward and omitted here.Illustration of the decomposition ofTui for any ui∈V.
(a)
Decomposition ofTui
(b)
Decomposition ofVuiα(uj)
(c)
Decomposition ofVuiβ(uj)Lemma 2.
Given any〈ui,uj〉 of T, one has
(6)Vui=Vuiα(uj)⊕Vuiβ(uj),
in which
(7)Vuiα(uj)=(⨁s∈Cui(uj)Vuiα(s))⊕{uj},(8)Vuiβ(uj)=(⨁w∈𝒬ui(uj)⨁s∈Cuiuj(w)Vuiα(s))⊕𝒬ui(uj).Lemma 3.
Given any treeTu=(Vu,Eu) rooted at u, one has,
(9)∑v∈Vu‍|𝒬u(v)|≤12|Vu|(|Vu|-1).Proof.
LetTu=(Vu,Eu) be a tree rooted at u with an arbitrary topology and TuΔ=(VuΔ,EuΔ) a line with the same number of nodes as Tu. First, we prove that ∑v∈Vu‍|𝒬u(v)|≤∑v∈VuΔ‍|𝒬uΔ(v)|. In fact, Tu can always be derived from TuΔ in the following way. Let L denote the current line and set L=TuΔ initially. We take away the lowest node of L and attach it to another node one by one. Every time we take away the lowest node of L, we set the rest of L to the current line. So, we are sure to obtain a series of trees rooted at u. Suppose that we get m trees, Tu1,Tu2,…,Tum in order. Let Tu0=TuΔ and ak=∑v∈Vu‍|𝒬uk(v)|, k=0,1,…,m. Given any 0≤k≤m-1, Tuk+1 is derived from Tuk by moving the lowest node v′ of L in Tuk. The new level in Tuk+1 at which v′ is located is lower than the previous level in Tuk. So, ak+1≤ak. Therefore, a0≥a1≥⋯≥am. Note that HuΔ=|VuΔ|-1 and |VuΔ(h)|=1, h=0,1,…,HuΔ. We have
(10)a0=∑v∈VuΔ|𝒬uΔ(v)|=∑h=1|VuΔ|-1h=12|VuΔ|(|VuΔ|-1).
Therefore, ∑v∈Vu‍|𝒬u(v)|≤(1/2)|Vu|(|Vu|-1) for any Tu.Lemma 4.
Given any treeTu=(Vu,Eu) rooted at u, one has,
(11)∑v∈Vu|Cu(v)|=|Vu|-1,(12)(|Vu|-1)2|Vu∖Du|≤∑v∈Vu|Cu(v)|2≤(|Vu|-1)2.Proof.
It follows directly fromCu(v)=∅, for all v∈Du and |Eu|=|Vu|-1, that ∑v∈Vu‍|Cu(v)|=∑v∈Vu∖Du‍|Cu(v)|=|Eu|=|Vu|-1.
On one hand,(13)∑v∈Vu|Cu(v)|2=∑v∈Vu∖Du|Cu(v)|2≥(∑v∈Vu∖Du|Cu(v)|)2|Vu∖Du|=(|Vu|-1)2|Vu∖Du|,
where the equality holds if and only if all |Cu(v)|, v∈Vu∖Du, are equal. Let Tu∘=(Vu∘,Eu∘) be a star rooted at u, say, a special case of Tu. On the other hand, we prove that ∑v∈Vu‍|Cu(v)|2≤∑v∈Vu∘‍|Cu∘(v)|2 for any Tu. Let m=|Vu∖Du| and n=|Vu|-1. We label all the nodes in Vu∖{u} by numbers 1,2,…,n. Let xk=|Cu(vk)|, k=1,…,m. Then we build the following restricted optimization problem:
(14)max∑k=1m‍xk2,s.t.∑k=1m‍xk=n,xk≥0,xk∈ℤ,k=1,…,m.
Without loss of generality, we suppose that max{x1,x2,…,xm}=xm. By taking xm=n-∑k=1m-1‍xk into the above objective function, we obtain a new unrestricted optimization problem
(15)maxxk≥0,xk∈ℤf(x1,…,xm-1)=∑k=1m-1‍xk2+(n-∑k=1m-1‍xk)2.
We conclude that, for every k=1,…,m-1,
(16)∂f∂xk=2xk-2(n-∑k=1m-1‍xk)=2(xk-xm)≤0.
Thus, fmax(x1,…,xm-1)=f(0,…,0)=n2 and xm=n. This implies that ∑v∈Vu‍|Cu(v)|2≤(|Vu|-1)2 and the tree rooted at u satisfying the equality is just Tu∘.Lemma 5.
Given any〈ui,uj〉 of T, one has
(17)Pr(ui,uj)=Pr(ui,v)Pr(v,uj),∀v∈V(π(ui,uj)).Proof.
First of all, for any two edge-disjoint pathsπ1 and π2 on T, we prove that π1 and π2 are independent. Suppose that π1 contains edges e1,e2,…,ek1 and π2 contains edges e1′,e2′,…,ek2′. It is obvious that {e1,e2,…,ek1}∩{e1′,e2′,…,ek2′}=∅. Since all of edges e∈E are independent, we conclude that
(18)Pr(π1π2)=∏i1=1k1‍Pr(ei1)∏i2=1k2‍Pr(ei2′)=Pr(π1)Pr(π2).
For any v∈V(π(ui,uj)), π(ui,uj) comprises two edge-disjoint subpaths π(ui,v) and π(v,uj). Therefore, Pr(ui,uj)=Pr(ui,v)Pr(v,uj).Lemma 6.
Given any〈ui,uj〉 of  T and v∈Vui,(i)
ifv∈𝒬ui(uj), then
(19)ℱ1(ui,uj;v)=max{Pr(ui,v),Pr(uj,v)},(20)ℱ2(ui,uj;v)=Pr(ui,v)+Pr(uj,v)-Pr(ui,v)Pr(uj,v),(ii)
ifv∈Vuiα(uj), then
(21)ℱλ(ui,uj;v)=Pr(uj,v),λ=1,2,(iii)
ifv∈Vuiα(s), where s∈Cuiuj(w) and w∈𝒬ui(uj), then
(22)ℱλ(ui,uj;v)=ℱλ(ui,uj;w)p(w,s)Pr(s,v),λ=1,2.Proof.
(i) Whenv∈𝒬ui(uj), it follows directly from the definition of ℱ1(ui,uj;v) that ℱ1(ui,uj;v)=max{Pr(ui,v),Pr(uj,v)}. We see that π(ui,uj) can be partitioned at v into two edge-disjoint subpaths π(ui,v) and π(uj,v). Lemma 5 implies that π(ui,v) and π(uj,v) are independent. The definition of ℱ2(ui,uj;v) means that the value of ℱ2(ui,uj;v) is equal to the probability of π(ui,v)∪π(uj,v). So,
(23)ℱ2(ui,uj;v)=Pr(π(ui,v)∪π(uj,v))=Pr(π(ui,v))+Pr(π(uj,v))-Pr(π(ui,v)∩π(uj,v))=Pr(ui,v)+Pr(uj,v)-Pr(ui,v)Pr(uj,v).
(ii) Whenv∈Vuiα(uj), π(ui,v) is composed of two edge-disjoint subpaths π(ui,uj) and π(uj,v). It follows from Lemma 5 that Pr(ui,v)=Pr(ui,uj)Pr(uj,v). So,
(24)ℱ1(ui,uj;v)=max{Pr(ui,uj),1}Pr(uj,v)=Pr(uj,v).
We see that π(ui,v) works correctly if and only if π(ui,uj) and π(uj,v) work correctly simultaneously. So, π(ui,v)=π(ui,uj)∩π(uj,v). Thus,
(25)ℱ2(ui,uj;v)=Pr((π(ui,uj)∩π(uj,v))∪π(uj,v))=Pr(uj,v).
(iii) Whenv∈Vuiα(s), where s∈Cuiuj(w) and w∈𝒬ui(uj), we observe that π(uk,v), k=i,j, consists of two edge-disjoint subpaths π(uk,w) and π(w,v). Also, π(w,v) comprises two edge-disjoint subpaths π(w,s) and π(s,v) as well. We derive that Pr(uk,v)=Pr(uk,w)p(w,s)Pr(s,v) from Lemma 5. So,
(26)ℱ1(ui,uj;v)=max{Pr(ui,v),Pr(uj,v)}=max{Pr(ui,w),Pr(uj,w)}p(w,s)Pr(s,v)=ℱ1(ui,uj;w)p(w,s)Pr(s,v).
We see thatπ(uk,v), k=i,j, works correctly if and only if π(uk,w) and π(w,v) work correctly simultaneously. So, π(uk,v)=π(uk,w)∩π(w,v). Thus,
(27)ℱ2(ui,uj;v)=Pr((π(ui,w)∩π(w,v))∪(π(uj,w)∩π(w,v)))=Pr(π(ui,w)∩π(w,v))+Pr(π(uj,w)∩π(w,v))-Pr((π(ui,w)∩π(w,v))∩(π(uj,w)∩π(w,v)))=Pr(ui,w)Pr(w,v)+Pr(uj,w)Pr(w,v)-Pr(ui,w)Pr(uj,w)Pr(w,v)=ℱ2(ui,uj;w)p(w,u)Pr(u,v).


## 3. Algorithm for Finding a Sum-Max 2-MRS

Definition 7.
GivenT=(V,E,p) and 〈ui,uj〉 of T, one lets 𝔼uiλ[uj], λ=1,2, denote the sum reachability in Tui of 〈ui,uj〉. In addition, one lets 𝒳uiλ(uj) (resp., 𝒴uiλ(uj)) denote the sum reachability in Vuiα(uj) (resp., Vuiβ(uj)) of 〈ui,uj〉.Theorem 8.
Given any〈ui,uj〉 of  T, if uj∈Vui, then one gets
(28)𝔼uiλ[uj]=𝒳uiλ(uj)+𝒴uiλ(uj),λ=1,2.Proof.
It follows directly from the definition of𝔼uiλ[uj] given in Definition 7 that 𝔼λ[ui,uj]=𝔼uiλ[uj]=𝔼ujλ[ui]. We further derive from (2) that 𝔼uiλ[uj]=∑v∈Vui‍ℱλ(ui,uj;v). By (6) in Lemma 2 together with the definitions of 𝒳uiλ(uj) and 𝒴uiλ(uj), we conclude that
(29)𝔼uiλ[uj]=∑v∈Vuiα(uj)ℱλ(ui,uj;v)+∑v∈Vuiβ(uj)ℱλ(ui,uj;v)=𝒳uiλ(uj)+𝒴uiλ(uj).Theorem 9.
Given any〈ui,uj〉 of  T, if uj∈Vui, then one gets
(30)𝒳uiλ(uj)=1+∑s∈Cui(uj)‍p(uj,s)𝒳uiλ(s),(31)𝒴uiλ(uj)=∑w∈𝒬ui(uj)‍ℱλ(ui,uj;w)×(𝒳uiλ(w)-p(w,suiuj(w))𝒳uiλ(suiuj(w))).Proof.
The combination of the definition of𝒳uiλ(uj) and (21) in Lemma 6 yields that 𝒳uiλ(uj)=∑v∈Vuiα(uj)‍Pr(uj,v). According to (7) in Lemma 2, for any v∈Vuiα(uj), it is obvious that Pr(uj,uj)=1 if v=uj and otherwise there must be a child s of uj if Cui(uj)≠∅ such that v belongs to Vuiα(s). By Lemma 5, we obtain Pr(uj,v)=p(uj,s)Pr(s,v). Therefore, for all uj∈Vui∖{ui}, we have
(32)𝒳uiλ(uj)=1+∑s∈Cui(uj)‍p(uj,s)∑v∈Vuiα(s)Pr(s,v)=1+∑s∈Cui(uj)p(uj,s)𝒳uiλ(s).
The definition of𝒴uiλ(uj) means 𝒴uiλ(uj)=∑v∈Vuiβ(uj)‍ℱλ(ui,uj;v). According to (8) in Lemma 2, for any v∈Vuiβ(uj), we are sure that v is either in 𝒬ui(uj) or in Vuiα(s), where s is a child other than suiuj(w) of some node w in 𝒬ui(uj). We can use (19) when λ=1 and (20) when λ=2 to compute ℱλ(ui,uj;v) if v∈𝒬ui(uj) and use (22) otherwise. Thus, for all uj∈Vui∖{ui}, we have
(33)𝒴uiλ(uj)=∑v∈𝒬ui(uj)ℱλ(ui,uj;v)+∑w∈𝒬ui(uj)ℱλ(ui,uj;w)×∑s∈Cuiuj(w)p(w,s)∑v∈Vuiα(s)Pr(s,v)=∑w∈𝒬ui(uj)ℱλ(ui,uj;w)(1+∑s∈Cuiuj(w)p(w,s)𝒳uiλ(s))=∑w∈𝒬ui(uj)ℱλ(ui,uj;w)(𝒳uiλ(w)-p(w,suiuj(w))22222222222222222222222×𝒳uiλ(suiuj(w))).From (3), we conclude that
(34)𝔼λ[ui*,uj*]=maxui∈Vmaxuj∈Vui∖{ui}𝔼uiλ[uj].We can compute𝔼λ[ui*,uj*] in the following way: for any ui∈V, we first compute 𝔼uiλ[uj] for all uj∈Vui∖{ui} using (28) and then find the maximum among |V|-1 values of 𝔼uiλ[uj]. We finally get 𝔼λ[ui*,uj*] by determining the maximum of the above |V| maximums. This is essentially the main framework of our dynamic programming algorithm called SUM-MAX, shown in Algorithm 1. The key task is to compute all the values of 𝔼uiλ[uj]. We see from Theorem 10 that the essence of computing 𝔼uiλ[uj] is to compute 𝒳uiλ(uj) and 𝒴uiλ(uj), and further from Theorem 9 that we can compute 𝒳uiλ(uj) by (30) and 𝒴uiλ(uj) by (31). Specifically, we derive 𝒳uiλ(uj)=1 from Cui(uj)=∅ when uj is a leaf of  Tui and 𝒴uiλ(ui)=0 from 𝒬ui(ui)=∅ when uj=ui. Therefore, for any ui∈V, we can first compute all the values of 𝒳uiλ(uj), uj∈Vui, level by level from the bottom of Tui to the top and afterward compute all the values of 𝒴uiλ(uj), uj∈Vui, level by level likewise. Based on (31), we can accumulate the value of 𝒴uiλ(uj) from uj to ui generation by generation for reducing the space.Algorithm 1:Algorithm SUM-MAX.
Input: an undirected tree T=(V,E,p) with each edge e∈E having
a probability weightp(e)∈(0,1);
Output: a Sum-Max 2-MRS 〈u*,v*〉 of T.
Step 0
i
←
1;
Step 1 Use DFS to traverse T with ui as the origin, store the
resultant rooted treeTui, record fui(uj) and compute
Pr(ui,uj) for all uj∈V, and store Dui;
if  i≤|V|  then  i←i+1; goto Step 1;
else  i←1; goto Step 2; endif
Step 2  for  h=Hui,Hui-1,…,1,0  do
for all nodes uj on the h-level of Tui  do
𝒳uiλ(uj)←1;
if  uj∉Dui  then
Compute𝒳uiλ(uj) by (30);
else break; endif
endfor
endfor
Step 3  for  h=Hui,Hui-1,…,1,0  do
for all nodes uj on the h-level of Tui  do
𝒴uiλ(uj)←0;
if  uj≠ui  then
w←uj; k←h;
while  k≥1  do
w′←w; w←fui(w); suiuj(w)←w′; k←k-1;
Computeℱλ(ui,uj;w) by (19) or (20);
𝒴uiλ(uj)←𝒴uiλ(uj)+ℱλ(ui,uj;w)×
(𝒳uiλ(w)-p(w,suiuj(w))𝒳uiλ(suiuj(w)));
endwhile
else  goto Step 4;  endif
endfor
endfor
Step 4  for  j=1,2,…,|V|  do
if  j≠i  then
Compute𝔼uiλ[uj] by (28);
else break;  endif
endfor
if  i<|V|  then
i←i+1; goto Step 2;
else
Find the maximum of all the values of𝔼uiλ[uj] and
then determineui* and uj* by (34);
endifIn order to facilitate algorithmSUM-MAX working level by level, we need to transform T into a rooted tree at every ui∈V beforehand. For this purpose, we devise a preprocessing procedure called PREP. The major idea of procedure PREP is described roughly as follows: we use the depth-first search (DFS) method to traverse T. DFS starts from ui. Let 𝒬ui(ui)=∅ initially. When DFS reaches a new node v via the edge {u,v}, we set 𝒬ui(v)=𝒬ui(u)∪{u} and compute Pr(ui,v)=Pr(ui,u)p(u,v). This process is repeated until DFS ends. DFS with ui as the origin produces a tree rooted at the origin, say, Tui. All the |V| times DFS’s obtain all the values of Pr(u,v), for all u,v∈V, u≠v, which makes preparations for computing ℱλ(ui,uj;w), w∈𝒬ui(uj), and further 𝒴uiλ(uj) for any ui∈V and uj∈Vui. In addition, DFS also finds the set of all the leaves of Tui, say, Dui.Theorem 10.
Given an undirected treeT=(V,E,p), where each edge e∈E has an independent working probability 0<p(e)<1, algorithm SUM-MAX can find a Sum-Max 2-MRS of T correctly with a time complexity of  O((1/2)|V|3) and a space complexity of O(|V|2).Proof.
First, we analyze the time complexity ofSUM-MAX. Step 0 takes O(1) time. Step 1 runs |V| times DFS in total. In every running (i.e., for every i=1,2,…,|V|), Step 1 spends O(|V|) time to traverse T and store Tui, O(1) time to record fui(uj), O(1) time to compute Pr(ui,uj) for each uj∈V, and at most O(|V|) time to determine Dui. So, Step 1 takes O(|V|2) time in all. Next, SUM-MAX runs Step 2, Step 3, and Step 4 in order for every i=1,2,…,|V|. Step 2 and Step 3 are both based on the bottom-up dynamic programming. Step 2 computes all the values of 𝒳uiλ(uj), uj∈V, which takes O(|V|) time by (11). Step 3 computes all the values of 𝒴uiλ(uj), uj∈V, the time complexity of which is O(∑uj∈V‍|𝒬ui(uj)|)≤O((1/2)|V|2) by (9). Step 4 spends O(|V|) time to compute all the values of 𝔼ui(uj), uj∈V∖{ui}. Therefore, the time complexity of SUM-MAX is at most O((1/2)|V|3).
Next, we discuss the space complexity ofSUM-MAX. Step 0 occupies O(1) space. For every i=1,2,…,|V|, Step 1 requires O(|V|) space to store Tui, O(|V|) space to store all fui(uj), uj∈V, and Pr(ui,uj), respectively, and at most O(|V|) space to store Dui. Thus, Step 1 occupies O(|V|2) space in total. For every i=1,2,…,|V|, Step 2 requires O(|V|) space to store all the values of 𝒳uiλ(uj), uj∈V; Step 3 requires O(|V|) space to store 𝒴uiλ(uj), uj∈V, which dominates the space complexity of Step 3, and Step 4 requires O(|V|) space to store 𝔼uiλ(uj), uj∈V. Therefore, the space complexity of SUM-MAX is O(|V|2).


## 4. Algorithm for Finding a Min-Max 2-MRS

Definition 11.
GivenT=(V,E,p) and 〈ui,uj〉 of T, one lets 𝕄uiλ[uj],λ=1,2, denote the minimum reachability in Tui of 〈ui,uj〉. Also, one uses, ℐuiλ(uj) (resp., 𝒥uiλ(uj)) to denote the minimum reachability in Vuiα(uj) (resp., Vuiβ(uj)) of 〈ui,uj〉.Theorem 12.
Given any〈ui,uj〉 of  T, if uj∈Vui, then one gets
(35)𝕄uiλ[uj]=min{ℐuiλ(uj),𝒥uiλ(uj)},λ=1,2.Proof.
We first derive from the definition of𝕄uiλ[uj] in Definition 11 that 𝕄λ[ui,uj]=𝕄uiλ[uj]=𝕄ujλ[ui] and further from (4) that 𝕄uiλ[uj]=minv∈Vuiℱλ(ui,uj;v). Combining (6) in Lemma 2 and the definitions of ℐuiλ(uj) and 𝒥uiλ(uj), we conclude that
(36)𝕄uiλ[uj]=min{minv∈Vuiα(uj)ℱλ(ui,uj;v),minv∈Vuiβ(uj)ℱλ(ui,uj;v)}=min{ℐuiλ(uj),𝒥uiλ(uj)}.Theorem 13.
Given any〈ui,uj〉 of T, if uj∈Vui, then one gets
(37)ℐuiλ(uj)=mins∈Cui(uj)p(uj,s)ℐuiλ(s),(38)𝒥uiλ(uj)=minw∈𝒬ui(uj)ℱλ(ui,uj;w)mins∈Cuiuj(w)p(w,s)ℐuiλ(s).Proof.
From the definition ofℐuiλ(uj) and (21) in Lemma 6, we get that ℐuiλ(uj)=minv∈Vuiα(uj)Pr(uj,v). Combining (7) in Lemmas 2 and 5, we conclude that
(39)ℐuiλ(uj)=min{Pr(uj,uj),mins∈Cui(uj)minv∈Vuiα(s)Pr(uj,v)}=min{1,mins∈Cui(uj)p(uj,s)minv∈Vuiα(s)Pr(s,v)}=mins∈Cui(uj)p(uj,s)ℐuiλ(s).
We derive𝒥uiλ(uj)=minv∈Vuiβ(uj)ℱλ(ui,uj;v) from the definition of 𝒥uiλ(uj). Combining (8) in Lemma 2 and (22) in Lemma 6, we conclude that
(40)𝒥uiλ(uj)=min{mins∈Cuiuj(w)minv∈𝒬ui(uj)ℱλ(ui,uj;v),minw∈𝒬ui(uj)ℱλ(ui,uj;w)22222222×mins∈Cuiuj(w)p(w,s)minv∈Vuiα(s)Pr(s,v)}=minw∈𝒬ui(uj)ℱλ(ui,uj;w)min{1,mins∈Cuiuj(w)p(w,s)ℐuiλ(s)}=minw∈𝒬ui(uj)ℱλ(ui,uj;w)mins∈Cuiuj(w)p(w,s)ℐuiλ(s).From (5), we conclude that
(41)𝕄λ[ui⋆,uj⋆]=maxui∈Vmaxuj∈Vui∖{ui}𝕄uiλ[uj].
Observe that we can compute 𝕄λ[ui⋆,uj⋆] in the same way as computing 𝔼λ[ui*,uj*]. Therefore, we can devise a dynamic programming algorithm called MIN-MAX to find a min-max 2-MRS of T based on the framework of SUM-MAX. The detailed presentation of MIN-MAX is omitted here and its major procedure is described as follows. Step 0 and Step 1 of MIN-MAX are same as those of SUM-MAX, which spends O(|V|2) time and requires O(|V|2) space in total. Let
(42)𝒦uiuj,λ(s)=mins′∈Cui(uj)∖{s}p(uj,s′)ℐuiλ(s′),∀s∈Cui(uj).For every i=1,…,|V|, Step 2 of MIN-MAX computes all ℐuiλ(uj), uj∈V, by (37) bottom-up on Tui which takes O(|V|) time and requires O(|V|) space. Also, Step 2 computes all 𝒦uiuj,λ(s), s∈Cui(uj), by (42) which takes O(∑uj∈V‍|Cui(uj)|2) time and requires O(∑uj∈V‍|Cui(uj)|) space. By (12), we conclude that
(43)|V|2≥∑uj∈V|Cui(uj)|2≥|V|2|V∖Dui|≥|V|2|V∖D|+1.
Hence, the time complexity of Step 2 is Ω(|V|2). Also, we conclude by (11) that the space complexity of Step 2 is O(|V|)+O(∑uj∈V‍|Cui(uj)|)=O(|V|). By (38), we conclude that
(44)𝒥uiλ(uj)=minw∈𝒬ui(uj)ℱλ(ui,uj;w)𝒦uiw,λ(suiuj(w)).
For every uj∈V, Step 3 of MIN-MAX computes 𝒥uiλ(uj) using the method of comparing generation by generation amongst 𝒬ui(uj). In every comparison, Step 3 first computes ℱλ(ui,uj;w) and then 𝒥uiλ(uj) by (44). So, Step 3 spends O(|𝒬ui(uj)|) time and requires O(1) space for every uj∈V. Hence, Step 3 spends O(∑uj∈Vui‍|𝒬ui(uj)|)≤O((1/2)|V|2) time by Lemma 3 and requires O(|V|) space. Step 4 of MIN-MAX is same as that of SUM-MAX. Therefore, we obtain Theorem 14.Theorem 14.
Given an undirected treeT=(V,E,p), where each edge e∈E has an independent working probability 0<p(e)<1, algorithm MIN-MAX can find a Min-Max 2-MRS of T correctly with a time complexity of Ω(|V|3) and a space complexity of O(|V|2).


## 5. Numerical Results

In this section, we give an example tree with 35 nodes shown in Figure2 for illustrating algorithms SUM-MAX and MIN-MAX. The decimal associated with every edge of the tree represents its operational probability. All the nodes are labeled by numbers 00,01,02,…,34 in order. For ease of view and comparison, the data output by algorithms are corrected to four decimal places and listed in Table 1. We first introduce the notations shown in the first line of Table 1. Let
(45)𝔼uiλ[ujΔλ]=maxuj∈Vui∖{ui}𝔼uiλ[uj],λ=1,2,∀ui∈V.
And then by (34)
(46)𝔼λ[ui*,uj*]=maxui∈V𝔼uiλ[ujΔλ].
Similarly, let
(47)𝕄uiλ[uj∇λ]=maxuj∈Vui∖{ui}𝕄uiλ[uj],λ=1,2,∀ui∈V.
And then by (41)
(48)𝕄λ[ui⋆,uj⋆]=maxui∈V𝕄uiλ[uj∇λ].Table 1
All the major data produced bySUM-MAX and MIN-MAX.
u
i
u
j
Δ
1
𝔼
u
i
1
[
u
j
Δ
1
]
u
j
Δ
2
𝔼
u
i
2
[
u
j
Δ
2
]
u
j
∇
1
𝕄
u
i
1
[
u
j
∇
1
]
u
j
∇
2
𝕄
u
i
2
[
u
j
∇
2
]
00
23
33.9225
33
34.5400
26
0.9337
32
0.9573
01
23
34.0221
33
34.5495
27
0.9402
32
0.9578
02
23
33.8806
33
34.5358
23
0.9307
32
0.9571
03
23
34.1265
33
34.5441
28
0.9486
32
0.9586
04
23
34.0053
33
34.5387
27
0.9405
32
0.9579
05
23
33.8363
33
34.5223
23
0.9290
32
0.9569
06
23
33.9210
33
34.4942
27
0.9402
32
0.9578
07
23
34.0722
33
34.5079
28
0.9486
32
0.9587
08
26
34.1822
34
34.5031
28
0.9486
32
0.9594
09
23
34.1098
33
34.5543
28
0.9454
32
0.9673
10
23
34.0282
33
34.5723
27
0.9434
32
0.9665
11
19
33.8772
33
34.5555
26
0.9346
32
0.9656
12
23
33.9239
33
34.4945
27
0.9404
32
0.9579
13
26
34.0825
34
34.3685
28
0.9505
28
0.9505
14
23
33.8749
33
34.5319
27
0.9395
32
0.9660
15
23
33.9196
33
34.5699
27
0.9375
32
0.9658
16
08
34.0480
21
34.3445
18
0.9232
23
0.9274
17
08
34.0804
21
34.3436
18
0.9232
23
0.9274
18
08
34.1591
21
34.3338
23
0.9275
23
0.9275
19
08
34.0540
21
34.1940
27
0.9377
27
0.9377
20
08
33.9853
21
34.1965
26
0.9329
27
0.9375
21
19
33.8721
33
34.5577
23
0.9290
32
0.9651
22
08
33.9138
15
34.3392
18
0.9232
23
0.9273
23
08
34.1759
21
34.4128
00
0.9317
00
0.9317
24
08
33.8656
21
34.1872
23
0.9262
27
0.9373
25
08
33.7640
15
34.1887
18
0.9232
27
0.9371
26
08
34.1822
21
34.4471
01
0.9359
00
0.9359
27
08
34.1818
15
34.4928
03
0.9434
00
0.9434
28
08
34.1386
15
34.5332
13
0.9505
00
0.9539
29
08
34.1374
15
34.5331
13
0.9505
08
0.9539
30
08
34.0665
15
34.4416
00
0.9266
19
0.9357
31
08
34.0649
15
34.4872
01
0.9340
13
0.9430
32
08
34.0582
15
34.5631
13
0.9505
09
0.9673
33
08
34.0013
10
34.5723
13
0.9471
09
0.9671
34
08
33.9397
10
34.5677
13
0.9453
09
0.9669Table 2
Notations table.
Notation
Explanation
𝒢
=
(
𝒱
,
ℰ
,
p
)
An undirected connected graph
T
=
(
V
,
E
,
p
)
An undirected tree graph
T
u
=
(
V
u
,
E
u
,
p
)
A rooted version ofT with u as the root
{
u
,
v
}
An edge of graph
〈
u
,
v
〉
A node pair
π
(
u
,
v
)
A simple path connecting nodesu and v (also, the event that π(u,v) works correctly)
Pr
(
π
(
u
,
v
)
)
The probability ofπ(u,v) working correctly
Pr
(
u
,
v
)
The probability ofu reaching v
𝒱
(
π
(
u
,
v
)
)
The set of nodes onπ(u,v)
ℰ
(
π
(
u
,
v
)
)
The set of edges onπ(u,v)
C
u
(
v
)
The set of the children ofv in Tu
T
u
(
v
)
The subtree ofTu rooted at v
V
u
α
(
v
)
The set of nodes inTu(v)
V
u
β
(
v
)
The set of nodes outsideTu(v)
f
u
(
v
)
The parent ofv in Tu
𝒬
u
(
v
)
The set of ancestors ofv in Tu
s
u
v
(
w
)
The child ofw on π(u,v) in Tu
C
u
v
(
w
)
The set of children ofw in Tu other than suv(w)
H
u
The number of the most ancestors of node inTu
h
The current level ofTu (h=1,2,…,Hu+1)
V
u
(
h
)
The set of nodes on theh-level of Tu
D
The set of leaves ofT
D
u
The set of leaves ofTu
A
⊕
B
The union of two disjoint setsA and B
λ
=
1
The superior probability
λ
=
2
The united probability
ℱ
1
(
u
i
,
u
j
;
v
)
The superior probability of〈ui,uj〉 to v
ℱ
2
(
u
i
,
u
j
;
v
)
The united probability of〈ui,uj〉 to v
𝔼
λ
[
u
i
,
u
j
]
The sum reachability of〈ui,uj〉
𝔼
u
i
λ
[
u
j
]
The sum reachability inTui of 〈ui,uj〉
𝒳
u
i
λ
(
u
j
)
The sum reachability inVuiα(uj) of 〈ui,uj〉
𝒴
u
i
λ
(
u
j
)
The sum reachability inVuiβ(uj) of 〈ui,uj〉
𝕄
λ
[
u
i
,
u
j
]
The minimum reachability of〈ui,uj〉
𝕄
u
i
λ
[
u
j
]
The minimum reachability inTui of 〈ui,uj〉
ℐ
u
i
λ
(
u
j
)
The minimum reachability inVuiα(uj) of 〈ui,uj〉
𝒥
u
i
λ
(
u
j
)
The minimum reachability inVuiβ(uj) of 〈ui,uj〉Figure 2
An example tree with a probability weight on every edge.From Table1, it is easy to see that the maximum in the third column is 𝔼081[26]=𝔼261[08]=34.1822 and thus 〈8,26〉 is the unique Sum-Max 2-MRS of the tree under the superior probability. The maximum in the fifth column is 𝔼102[33]=𝔼332[10]=34.5723 and thus 〈10,33〉 is the unique Sum-Max 2-MRS of the tree under the united probability. Likewise, we can see easily that the maximum in the seventh column is
(49)𝕄k1[13]=0.9505,k=28,29,32,
and thus there are three pairs of Min-Max 2-MRS of the tree under the superior probability, that is,
(50)〈13,28〉,〈13,29〉,〈13,32〉.
The maximum in the ninth column is 𝕄092[32]=𝕄322[09]=0.9673 and thus 〈9,32〉 is the unique Min-Max 2-MRS of the tree under the united probability.


## 6. Discussions and Future Works

This paper suggested the models of superior probability and united probability of node pair and studied two kinds of 2-MRS problem (i.e., Sum-Max 2-MRS and Min-Max 2-MRS) in a tree with each edge having an independent working probability and all the nodes being immune to failures. The paper presentsO((1/2)|V|3)-time and O(|V|2)-space algorithm for finding a Sum-Max 2-MRS of the tree and Ω(|V|3)-time and O(|V|2)-space algorithm for finding a Min-Max 2-MRS. It is also interesting to study the 2-MRS problem in a series-parallel graph; see [7]. Two servers involved in the paper work synchronously. In a number of practical scenarios, however, one of two servers works and the other gets ready. In the case, we can first find the two most reachable nodes using the algorithms in [10, 20] and then placing two servers optimally by placing the working server at the most reachable node and the backup one at the second most reachable node.When we are given a large-scale graph, we need to place more than two servers to supply synchronous service for the whole network. It is of interest to study thek-MRS problem with k≥3. It seems that our method proposed in the paper cannot be directly generalized to the k-MRS problem. Thus new ideas are required.



---

*Source: 743908-2013-11-12.xml*