# Parameterized Optimization in Uncertain Graphs--A Survey and Some Results
### Uncertain Graphs-Definition and Semantics  
We consider the graphs with uncertain edges and certain vertices. An uncertain graph, denoted by \(\mathcal{G}\), is a triple that consists of a vertex set \(V\), an edge set \(E\) and a set of _outcomes_\(\{\mathcal{A}_{e}\mid e\in E\}\). For each edge \(e\in E\), the outcome \(\mathcal{A}_{e}\) is a set of values and an associated probability distribution on \(\mathcal{A}_{e}\). The outcome \(\mathcal{A}_{e}\) is considered to be an interval or a finite set. For each \(e\in E\), if the outcome \(\mathcal{A}_{e}\) is an interval, the associated probability distribution is called a continuous distribution, and if it is a finite set, the associated probability distribution is called a discrete distribution. In either case, the natural distribution is the uniform distribution. For the case in which for each edge \(e\in E\), \(\mathcal{A}_{e}\) is a closed interval \([\mathcal{L}_{e},\mathcal{U}_{e}]\), the probability that \(e\) gets specific value in \(\mathcal{L}_{e}<\mathcal{U}_{e}\) is \(\frac{1}{\mathcal{U}_{e}-\mathcal{L}_{e}}\). In case for each \(e\in E\), \(\mathcal{A}_{e}\) is a finite set under the uniform distribution, the probability that \(e\) gets a specific value from \(\mathcal{A}_{e}\) is \(\frac{1}{|\mathcal{A}_{e}|}\). Such uncertain graphs were the focus of the earliest results [5; 7; 9; 10] and we survey these in Section 1.2. However, in general, the uncertainty could be modeled by any probability distribution \(A_{e}\). Therefore, the uncertain graph is a succinct representation of the set of all edge weighted graphs such that for each edge \(e\) its weight is a value from \(\mathcal{A}_{e}\). This set is an uncountable set when \(\mathcal{A}_{e}\) is an interval and it is \(\prod_{e\in E}|\mathcal{A}_{e}|\) in case each \(e\in E\), \(A_{e}\) is a finite set. In this paper, we present our results for the case when for each edge \(e\), the outcome \(\mathcal{A}_{e}\) is the set of values \(\{0,1\}\). Naturally, \(0\) models the absence of an edge and \(1\) models the presence of an edge. An uncertain graph under this condition is a succinct representation of the set of all edge subgraphs of \(G=(V,E)\). In this case, the uncertain graph \(\mathcal{G}\) is represented as a triple \((V,E,p)\) where \(p:E\rightarrow[0,1]\) is a function defined on \(E\) and \(p(e)\) is said to be the survival probability of the edge \(e\). The failure probability of an edge \(e\) is \(1-p(e)\). The set of all graphs represented by an uncertain graph is well-known as the _possible world semantics_ (PWS) [17; 18] of the uncertain graph. For each \(E^{\prime}\subseteq E\), \(H=(V,E^{\prime})\) is called a _possible world_ of \(\mathcal{G}\) and this is denoted by the notation \(H\sqsubseteq\mathcal{G}\). For an uncertain graph \(\mathcal{G}=(V,E,p)\), there are \(2^{|E|}\) possible worlds. An uncertain graph and two of its possible worlds are illustrated in Figure 1.  
The probability associated with a possible world depends on the probability distributions on \(\mathcal{A}_{e}\) and, most importantly, the dependence among the edge samples. A _distribution model_ is a specification of the dependence among edge samples. Further, a distribution model uniquely determines a probability distribution on the possible worlds. For example, if the edge samples are all independent, the distribution model is called the Random Failure (RF) model. Under the RF model, the probability of a possible world \(H\) is given by \(P(H)=\prod_{e\in E(H)}p(e)\prod_{e\in E\setminus E(H)}(1-p(e))\). Based on the dependence among the edge samples, the literature is rich in different distributions on the possible worlds. The distributions of interest in this paper are the Random Failure (RF) model, Independent Cascade (IC) model, Set-based Dependency (SBD) model and the Linear Reliability Ordering (LRO) model. These distribution models are all well-motivated by practical considerations on uncertain graphs in influence maximization, facility location, network reliability, to name a few.