# Parameterized Optimization in Uncertain Graphs--A Survey and Some Results
## 4 Max-Exp-Cover-1-RF Problem is FPT by (Treewidth \(\boldsymbol{\cdot}\boldsymbol{\Delta}\))  
An instance of Max-Exp-Cover-1-RF consists of a tuple \(\langle\mathcal{G},w,k\rangle\) where \(\mathcal{G}=(V,E,p)\) is an uncertain graph, \(w\) is a function that assigns weight \(w(v)\) to each vertex \(v\), and \(k\) is the budget. The goal  
Figure 3: An example of leaf (\(\mathbf{a}\)), introduce (\(\mathbf{b}\)), forget (\(\mathbf{c}\)) and join (\(\mathbf{d}\)) nodes. Directed edges denote child to parent link. Figure 2: (\(\mathbf{a}\)) A graph with 9 vertices; (\(\mathbf{b}\)) An optimal tree decomposition with treewidth 3.  
is to find a set \(S\subseteq V\) such that \(|S|\leq k\) and the expected total weight of the vertices dominated by \(S\) is maximized. The expectation is computed over the probability distribution uniquely defined on the possible worlds by the RF model. We introduce the function \(\mathcal{C}\) which we refer to as the _coverage_ function. The two arguments of the coverage function are subsets \(T\) and \(S\) of the vertex set \(V\), and the value \(\mathcal{C}(T,S)\) is the expected coverage of \(T\) by \(S\), where the expectation is computed over the possible worlds. For any subsets \(S,T\subseteq V\), the _Coverage_ of \(T\) by \(S\), denoted by \(\mathcal{C}(T,S)\), is \(\sum_{v\in T}\mathcal{C}(v,S)\). For a vertex \(v\in V\) and \(S\subseteq V\), the expected coverage of \(v\) by the set \(S\), denoted by \(\mathcal{C}(v,S)\), is given by  
\[\mathcal{C}(v,S)= \begin{cases}w(v)&\text{ if }v\in S\\ w(v)\Big{(}1-\prod_{u\in S\cap N(v)}(1-p_{uv})\Big{)}&\text{ otherwise.}\end{cases}  \tag{1}\]  
Note that if a set is a singleton set, then we abuse notation a little and write the element instead of the set. Our algorithm for the Max-Exp-Cover-1-RF follows the classical bottom-up approach for dynamic programming based on the nice tree decomposition. We compute a certain number of candidate solutions for the subproblem at each node \(i\in H\), using only the candidate solution values maintained in the children of \(i\). At each node \(i\in H\), we have \((5\cdot 2^{\Delta})^{n_{i}}\) candidate solutions which are stored in a table denoted by \(T_{i}\). The final optimal solution is obtained from the solutions stored in \(T_{r}\) at the root node \(r\) of \(H\). At any node \(i\) in \(H\), the expected coverage of a vertex \(u\in X_{i}\) by a set \(S\) in the subproblem at node \(i\) in \(H\) is computed by decomposing \(N(u)\cap S\) carefully to avoid over-counting. Towards this end, we introduce notation for the coverage conditioned on the event that some edges have failed. We denote this event by a function \(f\) and call this the _surviving neighbors_ (SN) function. The SN-function \(f:V\to 2^{V}\) has the property that for each \(u\in V\), \(f(u)\subseteq N(u)\). In other words, we are interested in the expected coverage conditioned on the event that for each \(u\in V\), all the edges to vertices in \(N(u)\setminus f(u)\) have failed. Definition 6: Let \(u\) be a vertex and \(S\subseteq V\) be a set and \(f\) be an SN-function such that \(S\cap f(u)=S\cap N(u)\). The conditional coverage of \(u\) by \(S\) restricted by \(f\) is defined to be  
\[\mathcal{C}_{f}(u,S)=\Big{(}\prod_{v\in N(u)\setminus f(u)}(1-p(uv))\Big{)} \mathcal{C}(u,S\cap f(u))\]  
Extending this definition to sets, for any two vertex sets \(T,S\), we define \(\mathcal{C}_{f}(T,S)=\sum_{u\in T}\mathcal{C}_{f}(u,S)\). For each \(u\in V\), \(\mathcal{C}_{f}(u,S)\) is the expected coverage of \(u\) by \(S\cap f(u)\) conditioned on the event that \(u\) is not covered by any vertex from the set \(N(u)\setminus f(u)\). Further, \(\mathcal{C}_{f}(u,S)\) is the product of \(w(u)\) and the probability of sampling a subgraph \(G^{\prime}\subseteq G\) in which \(u\) has a neighbor in \(S\cap N(u)\) and no neighbor from \(N(u)\setminus f(u)\). We refer to \(\mathcal{C}_{f}(u,S)\) as the conditional coverage of \(u\) by \(S\) (we leave out the phrase _restricted by \(f\)_).