# Parameterized Optimization in Uncertain Graphs--A Survey and Some Results
### Survey of Optimization Problems in Uncertain Graphs
For \(r=1\), the Max-Exp-Cover-1-LRO problem is NP-complete on planar graphs and the hardness follows from the hardness of budgeted dominating set due to [PERSON] et al. [29]. The Max-Exp-Cover-1-LRO admits a \((1-\frac{1}{e})\)-approximation algorithm [12; 13]. Similarly, [PERSON] et al. [14] shows that the influence maximization under the IC distribution model and the LT distribution model has a \((1-\frac{1}{e})\) approximation algorithm. Both these results naturally follow due to the submodularity of the expected neighborhood size function, the monotonicity (as \(r\) increases) and submodularity of the expected coverage function and the result of [PERSON] et al. [39] on greedy maximization of submodular functions. In the setting of parameterized algorithms, the Max-Exp-Cover-1-LRO problem is W[1]-complete for solution size as the parameter and this follows from the hardness of budgeted dominating set problem. An FPT algorithm for the Max-Exp-Cover-1-LRO problem with treewidth as the parameter is presented in Reference [13]. Formally stated, given an instance \(\langle\mathcal{G}=(V,E,p),k\rangle\) of the Max-Exp-Cover-1-LRO problem, an optimal solution can be computed in time \(4^{\mathcal{O}(t)}n^{\mathcal{O}(1)}\) where \(t\) is the treewidth of the graph \(G=(V,E)\) which is presented in the input as a tree decomposition. **Finding Communities in Uncertain Graphs. ** Finding communities is a significant problem in social network and in bioinformatics. A natural graph theoretic model for a community is a dense subgraph. A well-known dense subgraph is the _core_. Given an integer \(d\), a graph \(G=(V,E)\) is said to be \(d\)-core if degree of every vertex \(v\in V\) is at least \(d\). The way of obtaining the unique maximal induced subgraph of a graph \(G\) which is a \(d\)-core is to repeatedly discard vertices of degree less than \(d\). If the procedure terminates with a non-empty graph, then the graph is a \(d\)-core of the graph \(G\). A vertex \(v\) is said to be in a \(d\)-core if there is a \(d\)-core which contains \(v\). This idea is generalized to the uncertain graph framework as follows: Given an uncertain graph \(\mathcal{G}=(V,E,p)\) and the distribution model is the RF model, the _\(d\)-core probability_ of a vertex \(v\in V\), denoted by \(q_{d}(v)\), is the probability that \(v\) is in the \(d\)-core of a possible world. In other words, \(q_{d}(v)=\sum\limits_{H\subseteq G}P(H)I(H,d,v)\), where \(I(H,d,v)\) is an indicator function that takes value one if and only if there is a \(d\)-core of \(H\) that contains \(v\), and \(P(H)\) is probability of the possible world \(H\). In this setting, we consider the \((d,\theta)\)-core problem defined by [PERSON] et al. [16]. We refer to this problem as the Individual Core problem and it is defined as follows. Definition 2 (Individual-Core): The input consists of an uncertain graph \(\mathcal{G}=(V,E,p)\), an integer \(d\) and a probability threshold \(\theta\in[0,1]\). The objective is to compute an \(S\subseteq V\) such that for each \(v\in S\), \(q_{d}(v)\geq\theta\). [PERSON] et al. [16] shows that the Individual-Core problem is NP-complete. Prior to the results of [PERSON] et al. [16], [PERSON] et al. [15] introduced the study of \(d\)-core problem in uncertain graphs. We refer to the \(d\)-core problem on uncertain graphs as the Probabilistic-Core problem defined the follows. **Definition 3** (Probabilistic-Core). : _Given an uncertain graph \(\mathcal{G}=(V,E,p)\), an integer \(d\) and a probability threshold \(\theta\in(0,1]\), then the aim of the Probabilistic-Core problem is to find a set \(K\subseteq V\) such that the \(\Pr(K\) is a \(d\)-core in \(\mathcal{G})\) is at least \(\theta\)._  
The problem of deciding on the existence of such a set \(K\) can be shown to be NP-hard using the hardness result given in Reference [16]. On the other hand, if \(p(e)=1\) for all \(e\in E\), then the \(d\)-problem is polynomial time solvable as described at the beginning of this discussion.