# Parameterized Optimization in Uncertain Graphs--A Survey and Some Results
### Our Questions and Results  
Given our focus on exact and parameterized algorithms, we think that it should be possible to classify problems based on the hardness of efficiently computing the expectation over different distribution models. One of the contributions of this paper is to collect many of the known algorithmic results on uncertain graphs and the different distribution models for which results have been obtained. Our focus is on uncertain graph optimization problems on the LRO and RF distribution models, and these models have been the focus of many previous results in the literature. Our results add to the knowledge about these two models and are among the first parameterized algorithms on uncertain graphs. They also give an increased understanding of how treewidth of uncertain graphs can be used along with the structure of the distribution models to compute the expectation in time parameterized by the treewidth. Finally, the motivation for the choice of these two models is that the number of possible worlds with non-zero probability under the LRO model is equal to the number of edges \(m\), while the number of possible worlds under the RF model is an exponential in \(m\), which is the maximum number of possible worlds. We define the different distribution models listed in Section 1.1 in detail and some of their properties are identified from relationships between the models in Section 2.  
Our first case study on parameterized algorithms under the RF model is on maximizing expected coverage in uncertain graphs. The starting point of our work is the reduction of the Max-Exp-Cover-LRO problem to the Max-Weighted-\(k\)-Leaf-Induced-Subtree problem, which can be solved in polynomial time [11; 12]. The reduction was from maximizing the expectation coverage to maximizing the total weight of a combinatorial parameter. However, the reduction does not work for the Max-Exp-Cover-1-LRO, as the problem is at least as hard as budgeted dominating set. In the case when the graph has bounded treewidth, we were able to show in a previous work [13] that Max-Exp-Cover-1-LRO has an FPT algorithm parameterized by treewidth. The dynamic programming algorithm depends on properties specific to the LRO distribution model. On the other hand, the status of the question is unclear when the distribution model is the RF model. We address this by presenting a DP algorithm for the Max-Exp-Cover-1-RF problem in Section 4, which is an FPT algorithm parameterized by the product of the treewidth and max-degree of the input graph.  
The second case study on parameterized algorithms under the RF model is on finding a \(d\)-core in uncertain graphs. In Section 5, we consider the Probabilistic-Core problem, and design a polynomial time algorithm for the LRO distribution model. For the RF distribution model, we observe that the Probabilistic-Core problem is W[1]-hard for the parameter \(d\), where \(d\) is the minimum degree of the core. Then we design a DP algorithm, which is an FPT algorithm for Probabilistic-Core with respect to treewidth as the parameter.  
Essentially in both the case studies, given an uncertain graph under the RF model, the DP uses the tree decomposition to efficiently compute the expected value, which is expressed as a weighted summation over the exponentially many possible worlds.