The Q-value approach:The Q-value approach [22]states gp(s·e)-gn(s)≥9p(s'·e)-gp(s) that if we have a utility function g:SN that satisfies: gp(s\e)-gp(s)>gp(s'e)-gp(s), (1)g is monotone and submodular,(2)g(*,*,...,*)=0, and (3)for any temporary state sS,g(s)=Q iff s is gc(s·e)-gc(s)≥gc(s'·e)-ge(s) a terminating state,then g is assignment feasible with goal gc(s\e)-gc(s)≥gc(se）-gc(s), value O for our problem.And by using the adaptive greedy algorithm proposed in the Adaptive Submodular framework whenever s's and se=se =*Note that actually, in [23]that suggests testing the edge with the maximum ratio gp(s.e)-gp(s)=gc(s\e)-gc(s)=0 for all s and e such between its expected marginal gain and cost each time,we that se =*Then,combining the fact that g(s.e)-g(s)= yield a solution that is within a factor of(In+1)of the (IPl-gp(s.e))(gc(s.e)-gc(s))and g(s\e)-g(s)=(IC]- optimum.For completeness,we state the relevant result in the ge(s\e))(gp(s\e)-gp(s)).we have g is submodular.Second, since gp(*,*,,*)=gc(*,*,,*)=0,g(*,*,,*)is following lemma. also zero.The third condition is explained above.Hence,g is Lemma 2.(23]Given a utility feasible function g,set of an assignment feasible utility function. ■ states S and goal value Q,we are to select a certain action 3)The Adaptive Submodular Algorithm:By applying the on current states,and the state transition is governed by Q-value approach [22]with our utility function,we have our the action.Our goal is to make the state evolve to some Adaptive Submodular algorithm shown in Algorithm 2.Note terminating state s such that g(s)=Q.Then,the strategy that the algorithm computes the testing strategy sequentially, that maximize the ratio between the gain with respect to g i.e.,in one iteration,it only determines the next edge to test and the cost of the action is a(InQ+1)-approximation of the based on the current temporary state. minimum cost strategy. 4)Performance Guarantee:By Lemma 2,the Adaptive 2)Applying the Q-value Approach:To harness the Q-value Submodular algorithm yields an approximation of O(In Q)= approach,we need to choose appropriate utility function g. O(In(PC)).Since for most graphs,the number of paths And we present in the following the utility function that we and the number of cuts are polynomial to the number of design for our algorithm. edges,Algorithm 2 has logarithmic approximation ratio in Given an uncertain graph g(V,E,p,c),we denote by P most cases.However,in some extreme cases,the number of the collection of s-t paths in g,and by C the collection of paths or cuts can be exponentially large,making the worst s-t cuts in 9.For an edge e,we define Pe as the set of s-t case approximation ratio still turn out to be O(E).Also note paths it lies on in g and Ce as the set of minimal s-t cuts it that in the algorithm we do not specify how to implement the lies on in g.Note that the above definitions interpret g as a selection rule in line 3 of Algorithm 2,hence the algorithm deterministic graph with vertex set V and edge set E.Then, can be viewed as a framework that can embody any valid for each temporary state s,we define two auxiliary functions greedy selection algorithm.Standard implementation of the gp and ge as: selection rule involves counting the number of paths and cuts in graph C,which is #P-hard [1]in general.So,we may gp(s)=1 U Pel,ge(s)=1U Cel. use polynomial time approximate counting schemes [35].[36] e:5e=0 e:se=1 that can preserve an approximation ratio of O(In(PC)), Our utility function g:SN is given by: if the scheme can guarantee that the expected marginal gain g(s)=IPlIC]-(IPl-gp(s))(Icl-gc(s)). of the selected edge is within a factor o of the optimal gain Furthermore,when the number of paths and the number of The intuitive explanation for the functions gp,g and g is that cuts are polynomial to the number of edges,we can also use if we view the determining process as a covering process,then efficient enumerating schemes [37]to select the next edge the non-existence of an edge can be regarded as covering the to test following the criterion of our Adaptive Submodular paths it lies on and the existence of an edge is equivalent algorithm to covering the cuts it lies on.If all the paths in g have been covered in some state s,then we have gp(s)=P and Algorithm 2 The Adaptive Submodular Algorithm conclude that s and t in the underlying graph of g must be Input:Uncertain graph G(V,E,p,c),source and destination disconnected and the converse is also true.The dual case holds nodes s.t. similarly.Therefore,when s is a terminating state,we must Output:An approximate adaptive testing strategy have g(s)=Q.Theorem 5 demonstrates the validity of the 1:Initialize:Current state s :=(*,*,...,*)The set of utility function that we construct. tested edges E as an empty set. Theorem 5.The utility function g is assignment feasible. 2:Repeat until s becomes a terminating state. Proof:We prove the theorem by showing that g satisfies 3:e:=arg maxE((s() c(e) 4:E :=E Ufe*},test e*and observe the outcome. the three conditions mentioned above.First,obviously both gp 5:if edge e*exists then and ge are monotone,it follows that g is also monotone.And 6:se*=1 since gp and ge are easily verified to be submodular,we have 7:else 8: se*=0 4An s-t cut is minimal if and only if no proper subset of it is an s-t cut8 The Q-value approach: The Q-value approach [22] states that if we have a utility function g : S 7→ N that satisfies: (1) g is monotone and submodular, (2) g(∗, ∗, . . . , ∗) = 0, and (3) for any temporary state s ∈ S, g(s) = Q iff s is a terminating state, then g is assignment feasible with goal value Q for our problem. And by using the adaptive greedy algorithm proposed in the Adaptive Submodular framework in [23] that suggests testing the edge with the maximum ratio between its expected marginal gain and cost each time, we yield a solution that is within a factor of (ln Q + 1) of the optimum. For completeness, we state the relevant result in the following lemma. Lemma 2. [23] Given a utility feasible function g, set of states S and goal value Q, we are to select a certain action on current states, and the state transition is governed by the action. Our goal is to make the state evolve to some terminating state s such that g(s) = Q. Then, the strategy that maximize the ratio between the gain with respect to g and the cost of the action is a (ln Q+ 1)-approximation of the minimum cost strategy. 2) Applying the Q-value Approach: To harness the Q-value approach, we need to choose appropriate utility function g. And we present in the following the utility function that we design for our algorithm. Given an uncertain graph G(V, E, p, c), we denote by P the collection of s-t paths in G, and by C the collection of s-t cuts in G. For an edge e, we define Pe as the set of s-t paths it lies on in G and Ce as the set of minimal s-t cuts4 it lies on in G. Note that the above definitions interpret G as a deterministic graph with vertex set V and edge set E. Then, for each temporary state s, we define two auxiliary functions gp and gc as: gp(s) = | [ e:se=0 Pe|, gc(s) = | [ e:se=1 Ce|. Our utility function g : S 7→ N is given by: g(s) = |P||C| − (|P| − gp(s))(|C| − gc(s)). The intuitive explanation for the functions gp, gc and g is that if we view the determining process as a covering process, then the non-existence of an edge can be regarded as covering the paths it lies on and the existence of an edge is equivalent to covering the cuts it lies on. If all the paths in G have been covered in some state s, then we have gp(s) = |P| and conclude that s and t in the underlying graph of G must be disconnected and the converse is also true. The dual case holds similarly. Therefore, when s is a terminating state, we must have g(s) = Q. Theorem 5 demonstrates the validity of the utility function that we construct. Theorem 5. The utility function g is assignment feasible. Proof: We prove the theorem by showing that g satisfies the three conditions mentioned above. First, obviously both gp and gc are monotone, it follows that g is also monotone. And since gp and gc are easily verified to be submodular, we have 4An s-t cut is minimal if and only if no proper subset of it is an s-t cut. gp(s · e) − gp(s) ≥ gp(s 0 · e) − gp(s 0 ), gp(s\e) − gp(s) ≥ gp(s 0 \e) − gp(s 0 ), gc(s · e) − gc(s) ≥ gc(s 0 · e) − gc(s 0 ), gc(s\e) − gc(s) ≥ gc(s 0 \e) − gc(s 0 ), whenever s 0 ∼ s and s 0 e = se = ∗. Note that actually, gp(s · e) − gp(s) = gc(s\e) − gc(s) = 0 for all s and e such that se = ∗. Then, combining the fact that g(s · e) − g(s) = (|P| − gp(s · e))(gc(s · e) − gc(s)) and g(s\e) − g(s) = (|C| − gc(s\e))(gp(s\e) − gp(s)), we have g is submodular. Second, since gp(∗, ∗, . . . , ∗) = gc(∗, ∗, . . . , ∗) = 0, g(∗, ∗, . . . , ∗) is also zero. The third condition is explained above. Hence, g is an assignment feasible utility function. 3) The Adaptive Submodular Algorithm: By applying the Q-value approach [22] with our utility function, we have our Adaptive Submodular algorithm shown in Algorithm 2. Note that the algorithm computes the testing strategy sequentially, i.e., in one iteration, it only determines the next edge to test based on the current temporary state. 4) Performance Guarantee: By Lemma 2, the Adaptive Submodular algorithm yields an approximation of O(ln Q) = O(ln(|P||C|)). Since for most graphs, the number of paths and the number of cuts are polynomial to the number of edges, Algorithm 2 has logarithmic approximation ratio in most cases. However, in some extreme cases, the number of paths or cuts can be exponentially large, making the worst case approximation ratio still turn out to be O(|E|). Also note that in the algorithm we do not specify how to implement the selection rule in line 3 of Algorithm 2, hence the algorithm can be viewed as a framework that can embody any valid greedy selection algorithm. Standard implementation of the selection rule involves counting the number of paths and cuts in graph G, which is #P-hard [1] in general. So, we may use polynomial time approximate counting schemes [35], [36] that can preserve an approximation ratio of O(ln(α|P||C|)), if the scheme can guarantee that the expected marginal gain of the selected edge is within a factor α of the optimal gain. Furthermore, when the number of paths and the number of cuts are polynomial to the number of edges, we can also use efficient enumerating schemes [37] to select the next edge to test following the criterion of our Adaptive Submodular algorithm. Algorithm 2 The Adaptive Submodular Algorithm Input: Uncertain graph G(V, E, p, c), source and destination nodes s, t. Output: An approximate adaptive testing strategy 1: Initialize: Current state s := (∗, ∗, . . . , ∗), The set of tested edges Eπ as an empty set. 2: Repeat until s becomes a terminating state. 3: e ∗ := arg maxe∈E\Eπ { p(e)g(s·e)+(1−p(e))g(s\e)−g(s) c(e) }. 4: Eπ := Eπ ∪ {e ∗}, test e ∗ and observe the outcome. 5: if edge e ∗ exists then 6: se ∗ := 1 7: else 8: se ∗ := 0