of a is given by: whole network structure,it is reasonable to render the link Cost)=∑[Pr(G)∑c(el existence between nodes as a preassigned probability.And the algorithm for the problem thus helps us more efficiently GEg e∈Er(G) discover the relationship between nodes,which manifests its where (c)c(e)equals to the cost incurred by when significant use in link prediction [311.Moreover,the structure the underlying graph is G,and the expected cost is the weight- of the social networks can also be revealed [32],[33]by ed sum of the costs incurred on all the possible underlying applying the algorithm to different node pairs.Last but not graphs.An example of an adaptive testing strategy on an least,more potential applications of the illustrated scenario uncertain graph is illustrated in Figure 2. also include sensor networks [28],P2P networks [29]and Data Based on all the conditions above,now we give a formal center networks [7]. definition of our problem stated as follows. IV.COMPUTATIONAL COMPLEXITY Definition 3.(The Connectivity Determination Problem)Giv- en an uncertain directed graph2g(V,E,p,c)with two nodes In this section,we investigate the computational complexity s,t EV designated as source and destination,respectively, of the Connectivity Determination problem.By demonstrating the goal is to find an adaptive testing strategy n that incurs the hardness of two closely related problems,we show both the minimum expected cost. computing the testing strategy with the minimum expected cost holistically and sequentially are NP-hard.More specifically, Remark:Apart from deriving the strategy's action in all we first convert our problem into its corresponding decision temporary states at once,an algorithm for the Connectivity version that asks for the existence of an adaptive testing Determination problem can instead compute the strategy se- strategy with expected cost less than some value l for a given quentially,only deciding the next edge to test based on the uncertain graph.Then.we consider the problem of deciding current state.In algorithmic point of view,we consider the which edge to test first in the optimal strategy.The inherent time complexity of an algorithm for Connectivity Determina-tension of the Connectivity Determination problem is therefore tion problem as the maximum time it takes to compute all the disclosed through demonstrating the NP-hardness of these two relevant actions of a determining process.Therefore,finding problems,as stated in Theorems 1 and 2,respectively. the optimal strategy in a sequential fashion,on the surface, may appear to simplify the problem compared to computing it Theorem 1.The decision version of Connectivity Determina- holistically.However,we show in next section that the problem tion Problem is NP-hard. is NP-hard regardless of in which way we compute the optimal Proof:Inspired by [27],we prove the theorem by re- strategy.Table I summarizes the notations that will be used duction from the s-t reliability problem [1]:Given a directed throughout the paper. graph G and two nodes s and t.The s-t reliability is to Applicability of the model:We illustrate how to project our compute the probability of s being connected to t assuming model into real situations using several examples.Let us firstly the edges in G exist independently with probability As s-t take communication networks for example,where the edge reliability problem is #P-hard [1]3,its decision version that existence probability corresponds to the reliability of network quests whether the probability of s being connected to t is links.The testing cost represents the probing costs of the links. larger than some predefined value ro is NP-hard. The connectivity determination problem asks for a minimum The reduction works as follows.For a graph G(V,E),we cost probing strategy determining the source-destination con- transform it to an uncertain graph G(V,E',p,c)by adding an nectivity of the networks,allowing for the prevalent existence edge M between s.t and set the rest of g is just the same of edge uncertainty.Other than communication networks,such as G.Define n as the number of edges in G.We set the cost uncertain graph can also be projected into the structure of a of M as c(M)=n2+1 and the cost of testing other edges priced information,with each edge representing a piece of as 1.Then we assign the existence probability of all edges in information (data)and its testing cost corresponds to the price g as Finally,we designate s,t in g as the source and the of the data.Under such circumstance,the optimal strategy al- destination in the constructed instance. lows us to successfully query the information paying minimum Let r be the s-t reliability in G and I be the expected cost price [30].Another application is a social network graph where incurred by the optimal testing strategy on g.We define a an edge can be treated as a first cousin relationship,and the generic G'as a subgraph resulted from an underlying graph object of interest is to determine whether two individuals from of G with edge M removed.We will show that if we know l, a large population are distant cousins.Obviously,determining then we can efficiently compute r. whether an edge exists between two individuals is usually First,from the definitions,we have r=for some very expensive,involving costly genetic testing that outweighs integer k,and I must obey the following two constraints: any computational cost.An edge could of course represent I>(1-r)c(M)and I<rn +(1-r)c(M).Here,the a variety of other relationships that are expensive to check,first inequality follows from the fact that we have to test M for instance due to confidentiality or physical restrictions.In whenever we find out that s and t is not connected in G those scenarios where users have no prior knowledge of the The second inequality holds since the expected cost of the 2Without loss of generality.we assume the graph with vertex set V and 3#P is a complexity class for counting problems.#P-hard is at least as hard edge set E is s-t connected,i.e.,g is s-t connected if all its edges exist. as NP-hard [1].4 of π is given by: Cost(π) = X G∈G [P r(G) X e∈Eπ(G) c(e)], where P e∈Eπ(G) c(e) equals to the cost incurred by π when the underlying graph is G, and the expected cost is the weight￾ed sum of the costs incurred on all the possible underlying graphs. An example of an adaptive testing strategy on an uncertain graph is illustrated in Figure 2. Based on all the conditions above, now we give a formal definition of our problem stated as follows. Definition 3. (The Connectivity Determination Problem) Giv￾en an uncertain directed graph2 G(V, E, p, c) with two nodes s, t ∈ V designated as source and destination, respectively, the goal is to find an adaptive testing strategy π that incurs the minimum expected cost. Remark: Apart from deriving the strategy’s action in all temporary states at once, an algorithm for the Connectivity Determination problem can instead compute the strategy se￾quentially, only deciding the next edge to test based on the current state. In algorithmic point of view, we consider the time complexity of an algorithm for Connectivity Determina￾tion problem as the maximum time it takes to compute all the relevant actions of a determining process. Therefore, finding the optimal strategy in a sequential fashion, on the surface, may appear to simplify the problem compared to computing it holistically. However, we show in next section that the problem is NP-hard regardless of in which way we compute the optimal strategy. Table I summarizes the notations that will be used throughout the paper. Applicability of the model: We illustrate how to project our model into real situations using several examples. Let us firstly take communication networks for example, where the edge existence probability corresponds to the reliability of network links. The testing cost represents the probing costs of the links. The connectivity determination problem asks for a minimum cost probing strategy determining the source-destination con￾nectivity of the networks, allowing for the prevalent existence of edge uncertainty. Other than communication networks, such uncertain graph can also be projected into the structure of a priced information, with each edge representing a piece of information (data) and its testing cost corresponds to the price of the data. Under such circumstance, the optimal strategy al￾lows us to successfully query the information paying minimum price [30]. Another application is a social network graph where an edge can be treated as a first cousin relationship, and the object of interest is to determine whether two individuals from a large population are distant cousins. Obviously, determining whether an edge exists between two individuals is usually very expensive, involving costly genetic testing that outweighs any computational cost. An edge could of course represent a variety of other relationships that are expensive to check, for instance due to confidentiality or physical restrictions. In those scenarios where users have no prior knowledge of the 2Without loss of generality, we assume the graph with vertex set V and edge set E is s-t connected, i.e., G is s-t connected if all its edges exist. whole network structure, it is reasonable to render the link existence between nodes as a preassigned probability. And the algorithm for the problem thus helps us more efficiently discover the relationship between nodes, which manifests its significant use in link prediction [31]. Moreover, the structure of the social networks can also be revealed [32], [33] by applying the algorithm to different node pairs. Last but not least, more potential applications of the illustrated scenario also include sensor networks [28], P2P networks [29] and Data center networks [7]. IV. COMPUTATIONAL COMPLEXITY In this section, we investigate the computational complexity of the Connectivity Determination problem. By demonstrating the hardness of two closely related problems, we show both computing the testing strategy with the minimum expected cost holistically and sequentially are NP-hard. More specifically, we first convert our problem into its corresponding decision version that asks for the existence of an adaptive testing strategy with expected cost less than some value l for a given uncertain graph. Then, we consider the problem of deciding which edge to test first in the optimal strategy. The inherent tension of the Connectivity Determination problem is therefore disclosed through demonstrating the NP-hardness of these two problems, as stated in Theorems 1 and 2, respectively. Theorem 1. The decision version of Connectivity Determina￾tion Problem is NP-hard. Proof: Inspired by [27], we prove the theorem by re￾duction from the s-t reliability problem [1]: Given a directed graph G and two nodes s and t. The s-t reliability is to compute the probability of s being connected to t assuming the edges in G exist independently with probability 1 2 . As s-t reliability problem is #P-hard [1]3 , its decision version that quests whether the probability of s being connected to t is larger than some predefined value r0 is NP-hard. The reduction works as follows. For a graph G(V, E), we transform it to an uncertain graph G(V, E0 , p, c) by adding an edge M between s, t and set the rest of G is just the same as G. Define n as the number of edges in G. We set the cost of M as c(M) = n2 n+1 and the cost of testing other edges as 1. Then we assign the existence probability of all edges in G as 1 2 . Finally, we designate s, t in G as the source and the destination in the constructed instance. Let r be the s-t reliability in G and l be the expected cost incurred by the optimal testing strategy on G. We define a generic G0 as a subgraph resulted from an underlying graph of G with edge M removed. We will show that if we know l, then we can efficiently compute r. First, from the definitions, we have r = k 2n for some integer k, and l must obey the following two constraints: l ≥ (1 − r)c(M) and l ≤ rn + (1 − r)c(M) . Here, the first inequality follows from the fact that we have to test M whenever we find out that s and t is not connected in G0 . The second inequality holds since the expected cost of the 3#P is a complexity class for counting problems. #P-hard is at least as hard as NP-hard [1]