# Parameterized Optimization in Uncertain Graphs--A Survey and Some Results
### Survey of Optimization Problems in Uncertain Graphs  
Graphs have been used to represent the relationships between entities. A graph is denoted by \(G=(V,E)\) where \(V\) is set of vertices and \(E\subseteq V\times V\) is set of edges representing relationship between pairs of vertices. PPI networks in bioinformatics, road networks and social networks are graphs with an uncertainty among the edges and are considered as uncertain graphs. The earliest ideas in graphswith uncertain edge weights were introduced by [PERSON] and [PERSON] [9] in 1965. [PERSON] and [PERSON] studied the maximum flow in a directed graph \(G=(V,E)\) with uncertain capacities. On an input, consisting of an uncertain digraph \(G=(V,E)\) and a continuous random variable with the uniform probability distribution on the capacity of each edge \(e\), the probabilistic flow problem is to find the maximum flow probability and the joint distribution of the cut set values. Later in 1969, under the same setting [PERSON] [5] studied the probabilistic shortest path problem on an undirected graph \(G=(V,E)\). The probabilistic shortest path problem is to compute for each \(\ell\), the probability that the shortest path is at most \(\ell\). In 1976, [PERSON] [10] studied the probabilistic maximum flow in a directed acyclic graph (DAG) with a discrete probability distribution on the edge capacities. A relatively recent result in 2008 is on the minimum spanning tree problem on uncertain graphs, by [PERSON] et al. [7], with uncertain edge weights from a continuous distribution. Here the goal is to optimize the number of edges whose weight is sampled to obtain a spanning tree which achieves the expected MST weight over the possible worlds. This problem is different from the optimization problems of interest to us in this paper- given an uncertain graph as input, our goal is to optimize the expected value of a structural parameter over the possible worlds of the uncertain graph. Optimization problems on uncertain graphs related to connectedness are among the most fundamental problems. Apart from their practical significance, they pose significant algorithmic challenges in different computational models. Further, the computational complexity of the problems increases significantly in the presence of uncertainty. In 1979, [PERSON] [6] studied the network reliability problem on uncertain graphs. The network reliability problem is a well-studied #P-hard problem [6; 17; 20; 21; 22; 23]. The reliability problems have numerous applications in communication networks [24; 25], biological networks [3] and social networks [26; 27]. For a given network, _reliability_ is defined as the ability of the network to remain operational after the failure of some of its links. The input consists of an uncertain graph \(\mathcal{G}=(V,E,p)\) and a subset \(S\subseteq V\) and the aim is to compute the probability that \(S\) is connected. Clearly, the reliability problem on uncertain graphs generalizes the graph connectivity problem which is polynomial time solvable. The _Canadian Traveler Problem_ (CTP), formulated by [PERSON] and [PERSON] in 1991 [28], is an online problem on uncertain graphs. Given an uncertain graph \(\mathcal{G}=(V,E,p)\), a source \(s\) and a destination \(t\), a traveler must find a walk from \(s\) to \(t\), where an edge \(e\) is known to have survived with probability \(p(e)\) only when the walk reaches one of its end points, after which it does not fail, conditioned on it having survived. The objective is to minimize the expected path length over the distribution on the possible worlds and the walker's choices. **Coverage in Uncertain Graphs. ** Apart from the themes of network flows and connectedness, coverage problems are very practical when the uncertainty is on the survival of the edges. In this framework, the uncertainty is on whether an edge will survive a disaster and the goal is to place facilities in the network such that the expected coverage over the possible worlds is maximized.