3 uncertain networks incurring minimum cost.Furthermore,to heuristics as they achieve better tradeoff between the fully utilize the results of previous tests,the strategy should be complexity of the algorithm and the optimality of the adaptive,which means that we may determine the next edge to solutions. test based on the edge existence information we have already The rest of the paper is organized as follows.we review acquired through previous tests.And we defer a more detailed related studies in SectionⅡ.In SectionⅡ，.we formally explanation of how the problem of interest can be applied to introduce the definitions and notations related to our problem. other realistic scenarios to the end of Section III-B. In Section IV,we investigate the computational complexity In this paper,we are thus motivated to present a first of the problem.We present our exact dynamic programming look into the problem of determining source-destination con- algorithm based on Markov Decision Process framework in nectivity in uncertain networks.Given a network modeled Section V.In Section VI,we present the two approximation as an uncertain graph with each edge associated with an algorithms and we evaluate our algorithms on real life data existence probability and a testing cost,together with two in Section VII.We give concluding remarks as well as future network nodes s,t designated as source and destination,we directions in Section VIII. aim to derive efficient strategy specifying which edges to test so that we can verify whether s and t are connected II.RELATED WORK by a path or separated by a cut with the minimum cost incurred.Note that the source and destination connectivity 1)Uncertain Networks:Uncertain network has been under is also referred to as s-t connectivity.Comparing with s-t intensive study for long.However,instead of verifying the connectivity in deterministic graphs that can be easily solved existence of some structures in uncertain networks,most by graph traversal methods in polynomial time,by proving the efforts have been devoted to calculating the existence prob- NP-hardness of the problem,we find that the s-t connectivity ability of those structures.One of the fundamental problems in uncertain graphs turns out to be far more complicated in that regard is the network reliability problem,which asks and highly non-trivial.Driven by the necessity of pursuing the probability that uncertain networks are connected [1]. exact algorithms that can capture the features of the optimal Following this.Jin et al.consider the distance-constrained solutions,we proceed by converting our problem into an reachability,i.e..the probability that two nodes are connected equivalent Markov Decision Process (MDP)to give a dynamic by a path shorter than a predefined threshold in an uncertain programming algorithm that yields optimal strategies but has network [13].The work in [14]focuses on discovering sub- exponential running time.Considering that the prohibitive graphs with high reliability measure.In recent years,other time complexity of such exact algorithm renders it unsuitable types of study on uncertain networks(graphs)include reliable for practical applications,we therefore design approximation topology design [15],extracting representative subgraphs for schemes to compromise the optimality of computed strategy the acceleration of various querying processes [16],perfor- for the efficiency of the algorithms.In doing so,we first put mance analysis of unreliable wireless networks [8]as well as forward a simple greedy approach that computes near optimal connectivity and resilience of secure sensor networks [9]. solutions with linear approximation guarantee,which can be The modeling of uncertain networks in the present work is further improved by a second algorithm we propose through similar to random graph which was first introduced by Erdos the exploration of submodularity in our problem. and Renyi in [17].Despite of this similarity,the problems Our key contributions are summarized as follows: investigated are quite different.Specifically,previous works Theory:We formally define the problem of determining on random graphs [17][18]is dedicated to the analysis of s-t connectivity in uncertain networks.We prove compu- model property in an asymptotic sense where the number tational complexity-theoretic results of the problem show-of nodes goes to infinity.In contrast,our focus here lies in ing that it cannot be solved in polynomial time unless the combinatorial optimization problem formulated from the P=NP.The results provide useful insights to the inherent determination of source-destination connectivity in uncertain hardness and combinatoric nature of our problem. networks,with the model serving as a mean to characterize Algorithm:We derive an exact dynamic programming the uncertainty in networks and a parsimonious media for algorithm by converting our problem into an equivalent fi- extracting the essence of the problem. nite horizon Markov Decision Process.To further counter 2)Sequential Testing:The nature of our problem is analo- the problem,we design two approximation schemes.The gous to a class of sequential testing problems which involves first one is a simple greedy approach and we show that diagnosing a system by determining the states of its compo- naive as it is,it can provide non-trivial performance nents through a series of tests.The dependency of the whole guarantee.More surprisingly,its performance is far better system on its components'states can be given by explicit than some other more complicated algorithms.Then,we function or via an oracle.Existing results include optimal further improve the approximation ratio of the greedy diagnosing strategies on series and parallel systems,double algorithm by utilizing the submodularity of the problem regular systems,etc.See [19]for a comprehensive review.A in the second algorithm. special class of sequential testing problems called Stochastic Application:We demonstrate the effectiveness of our Boolean Function Evaluation (SBFE)have close connection algorithms on practical applications through extensive to our problem.In SBFE,each component has two states simulations with real network datasets.It is shown that and thus can be considered as a Boolean variable and the our proposed algorithms are superior to the conventional system is given by a Boolean function.The works in [20]and2 uncertain networks incurring minimum cost. Furthermore, to fully utilize the results of previous tests, the strategy should be adaptive, which means that we may determine the next edge to test based on the edge existence information we have already acquired through previous tests. And we defer a more detailed explanation of how the problem of interest can be applied to other realistic scenarios to the end of Section III-B. In this paper, we are thus motivated to present a first look into the problem of determining source-destination con￾nectivity in uncertain networks. Given a network modeled as an uncertain graph with each edge associated with an existence probability and a testing cost, together with two network nodes s, t designated as source and destination, we aim to derive efficient strategy specifying which edges to test so that we can verify whether s and t are connected by a path or separated by a cut with the minimum cost incurred. Note that the source and destination connectivity is also referred to as s-t connectivity. Comparing with s-t connectivity in deterministic graphs that can be easily solved by graph traversal methods in polynomial time, by proving the NP-hardness of the problem, we find that the s-t connectivity in uncertain graphs turns out to be far more complicated and highly non-trivial. Driven by the necessity of pursuing exact algorithms that can capture the features of the optimal solutions, we proceed by converting our problem into an equivalent Markov Decision Process (MDP) to give a dynamic programming algorithm that yields optimal strategies but has exponential running time. Considering that the prohibitive time complexity of such exact algorithm renders it unsuitable for practical applications, we therefore design approximation schemes to compromise the optimality of computed strategy for the efficiency of the algorithms. In doing so, we first put forward a simple greedy approach that computes near optimal solutions with linear approximation guarantee, which can be further improved by a second algorithm we propose through the exploration of submodularity in our problem. Our key contributions are summarized as follows: • Theory: We formally define the problem of determining s-t connectivity in uncertain networks. We prove compu￾tational complexity-theoretic results of the problem show￾ing that it cannot be solved in polynomial time unless P=NP. The results provide useful insights to the inherent hardness and combinatoric nature of our problem. • Algorithm: We derive an exact dynamic programming algorithm by converting our problem into an equivalent fi- nite horizon Markov Decision Process. To further counter the problem, we design two approximation schemes. The first one is a simple greedy approach and we show that naive as it is, it can provide non-trivial performance guarantee. More surprisingly, its performance is far better than some other more complicated algorithms. Then, we further improve the approximation ratio of the greedy algorithm by utilizing the submodularity of the problem in the second algorithm. • Application: We demonstrate the effectiveness of our algorithms on practical applications through extensive simulations with real network datasets. It is shown that our proposed algorithms are superior to the conventional heuristics as they achieve better tradeoff between the complexity of the algorithm and the optimality of the solutions. The rest of the paper is organized as follows. we review related studies in Section II. In Section III, we formally introduce the definitions and notations related to our problem. In Section IV, we investigate the computational complexity of the problem. We present our exact dynamic programming algorithm based on Markov Decision Process framework in Section V. In Section VI, we present the two approximation algorithms and we evaluate our algorithms on real life data in Section VII. We give concluding remarks as well as future directions in Section VIII. II. RELATED WORK 1) Uncertain Networks: Uncertain network has been under intensive study for long. However, instead of verifying the existence of some structures in uncertain networks, most efforts have been devoted to calculating the existence prob￾ability of those structures. One of the fundamental problems in that regard is the network reliability problem, which asks the probability that uncertain networks are connected [1]. Following this, Jin et al. consider the distance-constrained reachability, i.e., the probability that two nodes are connected by a path shorter than a predefined threshold in an uncertain network [13]. The work in [14] focuses on discovering sub￾graphs with high reliability measure. In recent years, other types of study on uncertain networks (graphs) include reliable topology design [15], extracting representative subgraphs for the acceleration of various querying processes [16], perfor￾mance analysis of unreliable wireless networks [8] as well as connectivity and resilience of secure sensor networks [9]. The modeling of uncertain networks in the present work is similar to random graph which was first introduced by Erdos¨ and Renyi in [17]. Despite of this similarity, the problems investigated are quite different. Specifically, previous works on random graphs [17] [18] is dedicated to the analysis of model property in an asymptotic sense where the number of nodes goes to infinity. In contrast, our focus here lies in the combinatorial optimization problem formulated from the determination of source-destination connectivity in uncertain networks, with the model serving as a mean to characterize the uncertainty in networks and a parsimonious media for extracting the essence of the problem. 2) Sequential Testing: The nature of our problem is analo￾gous to a class of sequential testing problems which involves diagnosing a system by determining the states of its compo￾nents through a series of tests. The dependency of the whole system on its components’ states can be given by explicit function or via an oracle. Existing results include optimal diagnosing strategies on series and parallel systems, double regular systems, etc. See [19] for a comprehensive review. A special class of sequential testing problems called Stochastic Boolean Function Evaluation (SBFE) have close connection to our problem. In SBFE, each component has two states and thus can be considered as a Boolean variable and the system is given by a Boolean function. The works in [20] and