# Parameterized Optimization in Uncertain Graphs--A Survey and Some Results
### Survey of Optimization Problems in Uncertain Graphs
Among these two models, the Independent Cascade model is defined as a sampling procedure whose outcome is an edge subgraph of a given uncertain graph. Thus, this model is more relevant for our study of uncertain graphs and the IC model is defined in Section 2. In the influence maximization problems considered in KKT [14], the aim is to select \(k\) influential people \(S\) such that the expected number of people connected to \(S\) is maximized. The expected number of vertices, over the distribution model, connected to a set \(S\) is called the influence of a set \(S\) or the expected coverage of \(S\) and is denoted by \(\sigma(S)\). Thus, the influence maximization problem is to find the set \(\underset{S\subseteq V,|S|=k}{\arg\max}\ \sigma(S)\). In Section 2, we discuss the computational complexity of \(\sigma(S)\) for different distribution models. Thus, the influence maximization problem in Reference [14] is essentially a facility location problem where the distribution model is specified by a diffusion phenomenon, \(r=\infty\) and each input instance consists of an uncertain network and a budget \(k\). **Coverage and Facility Location. ** The survey due to [PERSON] [33] in 2006 collects the vast body of results on the facility location problem in uncertain graphs into a single research article. The earliest result known to us, due to [PERSON] [19] who formulated the maximum expected coverage problem where vertices are uncertain, is different from our case where the uncertainty is on the edges and the vertices are known. To the best of our knowledge, it was [PERSON]'s work [19] that considered the general setting of dependence among vertex failures. In this case, the probability distribution would have been defined uniquely on the possible worlds which would have been the set of induced subgraphs. Subsequently, many variants of the facility location problem for uncertain graphs have been studied for different distribution models where the uncertainty is on the survival of edges. [PERSON] et al. [34] considered the problem with single edge failure and for \(r=\infty\). In this case, exactly one edge is assumed to have failed after a disaster and the objective is to place \(k\) facilities such that the expected weight of vertices not connected to any facility is minimized. In this case, each subgraph consisting of all the edges except one is a possible world. This problem is known to be polynomial time solvable for any \(k\geq 1\). When the distribution model is the Random Failure model and \(r=\infty\), the _most reliable source_ (MRS) is well-studied [35; 36; 37; 38]. The input is an uncertain graph and \(k=1\). The goal is to select one vertex \(v\) such that the expected number of vertices connected to \(v\) is maximized. [PERSON] and [PERSON] [38] gave a polynomial time algorithm for the MRS problem on trees, followed by linear time algorithm on uncertain trees by [PERSON] and [PERSON] [37]. [PERSON] and [PERSON] [35] gave an \(\mathcal{O}(n^{2})\)-time algorithm for the MRS problem on uncertain series-parallel graphs. [PERSON] [36] gave an \(\mathcal{O}(n^{2})\)-time algorithm for the MRS problem on uncertain ring graphs. Apart from the RF model, the Linear Reliability Ordering ( LRO) distribution model has been well-studied recently. Under this distribution model, for each integer \(r\geq 1\), the facility location problem is studied as Max-Exp-Cover-\(r\)-LRO problem [11; 12; 13]. For the case when \(r=\infty\), the problem is known as the Max-Exp-Cover-LRO problem. [PERSON] et al. [11] presented an algorithm to solve the Max-Exp-Cover-LRO problem via a reduction to the Max-Weighted-\(k\)-Leaf-Induced-Subtree problem. They then showed that the Max-Weighted-\(k\)-Leaf-Induced-Subtree problem can be solved in polynomial time on trees using a greedy algorithm. Consequently, they showed that the Max-Exp-Cover-LRO problem can be solved in polynomial time.