# 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}\))
### Recursive Formulation of the Value of a Solution  
Let \(S\subseteq V\) be a set of size \(k\) for the Max-Exp-Cover-1-RF problem in \(\mathcal{G}\). We now present a recursive formulation to compute the expected coverage of \(V\) by \(S\). Throughout this section \(S\) denotes this set of size \(k\). Let \(i\) be a node in \(H\). Let \(j\) and \(g\) be the children of \(i\). In case \(i\) is either introduce node or forget node, then \(g\) is considered to be a null node with \(X_{g}=X_{g}^{+}=\emptyset\). In node \(i\), let \(A=S\cap X_{i}\), \(S_{i}=S\cap X_{i}^{+}\) and \(Z_{i}=S_{i}\setminus A\). Let \(\hat{Z}=S\setminus S_{i}\). For the solution \(S\), the set \(X_{i}\) can be partitioned into five sets \((A,C,L,R,B)\) as follows. \[A=\{u\in X_{i}\cap S\}\] \[C=\{u\in X_{i}\setminus A\ |\ u\in N(A)\setminus N(Z_{i})\},\text{ in other words, $C$ satisfies $\mathcal{C}(C,Z_{i})=0$}\] \[L=\{u\in X_{i}\setminus A\ |\ u\in N(Z_{j})\setminus N(Z_{g})\}, \text{ in other words, $L$ satisfies $\mathcal{C}(L,Z_{g})=0$}\] \[R=\{u\in X_{i}\setminus A\ |\ u\in N(Z_{g}\setminus N(Z_{j}) \},\text{ in other words, $R$ satisfies $\mathcal{C}(R,Z_{j})=0$}\] \[B=\{u\in X_{i}\setminus A\ |\ u\in N(Z_{j})\cap N(Z_{g})\}.\]  
Further, for the solution \(S\), define the SN-function \(f:X_{i}^{+}\to 2^{V}\) as follows:  
\[f(u) = N(u)\setminus\{v\in N(u)\ |\ v\in\hat{Z}\},\text{if $u\in X_{i}$}\] \[= N(u),\text{if $u\in X_{i}^{+}\setminus X_{i}$}\]  
**Note:**\(f\) is dependent on \(S\) and \(i\) and wherever \(f\) is used, it must be used as per the definition at the corresponding node in the tree decomposition. Let \(S\subseteq V\) be a subset of size \(k\), \(i\) be a node in \(H\) in the nice tree decomposition, \(f\) be the SN-function for \(X_{i}^{+}\) defined using \(S\), \(\mathtt{P}=(A,C,L,R,B)\) be a partition of \(X_{i}\), and \(S_{i}\), \(Z_{i}\) and \(\hat{Z}\) be as defined above. The following two lemmas are useful in setting up a recursive definition of \(\mathcal{C}(V,S)\) and a bottom-up evaluation of the recurrence. **Lemma 3**: \(\mathcal{C}(V,S)=\mathcal{C}(V\setminus X_{i}^{+},\hat{Z}\cup A)+\mathcal{C}( X_{i}\setminus A,\hat{Z})+\mathcal{C}_{f}(X_{i}^{+},S_{i})\)_._  
**Proof. ** The expected coverage of \(V\) by the set \(S\) is given by \(\mathcal{C}(V,S)=\mathcal{C}(V\setminus X_{i}^{+},S)+\mathcal{C}(X_{i},S)+ \mathcal{C}(X_{i}^{+}\setminus X_{i},S)\). Since \(V\) is partitioned into three disjoint sets \(X_{i}\), \(X_{i}^{+}\setminus X_{i}\), and \(V\setminus X_{i}^{+}\), we get  
\[\mathcal{C}(V,S)=\mathcal{C}(V\setminus X_{i}^{+},\hat{Z}\cup A)+\mathcal{C}( X_{i}\setminus A,\hat{Z}\cup S_{i})+\mathcal{C}(A,S)+\mathcal{C}(X_{i}^{+} \setminus X_{i},S_{i}).\]  
By applying Lemma 2 to \(\mathcal{C}(X_{i}\setminus A,\hat{Z}\cup S_{i})\), it follows that  
\[\mathcal{C}(V,S)=\mathcal{C}(V\setminus X_{i}^{+},\hat{Z}\cup A)+\mathcal{C}( X_{i}\setminus A,\hat{Z})+\mathcal{C}_{f}(X_{i}\setminus A,S_{i})+\mathcal{C}(A,S)+ \mathcal{C}(X_{i}^{+}\setminus X_{i},S_{i}).\]Further, \(\mathcal{C}(A,S_{i})=\mathcal{C}(A,S)\), since \(\mathcal{C}(A,S_{i})=\mathcal{C}(A,S)=\sum_{v\in A}w(v)\), it follows that  
\[\mathcal{C}(V,S)=\mathcal{C}(V\setminus X_{i}^{+},\hat{Z}\cup A)+\mathcal{C}(X _{i}\setminus A,\hat{Z})+\mathcal{C}_{f}(X_{i}\setminus A,S_{i})+\mathcal{C}( A,S_{i})+\mathcal{C}(X_{i}^{+}\setminus X_{i},S_{i}).\]  
By the definition of \(f\) and \(\mathcal{C}_{f}\), \(\mathcal{C}_{f}(X_{i}\setminus A,S_{i})+\mathcal{C}(A,S_{i})+\mathcal{C}(X_{ i}^{+}\setminus X_{i},S_{i})=\mathcal{C}_{f}(X_{i}^{+},S_{i})\). Therefore we get \(\mathcal{C}(V,S)=\mathcal{C}(V\setminus X_{i}^{+},\hat{Z}\cup A)+\mathcal{C}( X_{i},\hat{Z})+\mathcal{C}_{f}(X_{i}^{+},S_{i})\). Hence the lemma. As a corollary it follows that \(\mathcal{C}(V,S)=\mathcal{C}_{f}(X_{r}^{+},S_{r})\). Recall that \(X_{r}=\emptyset_{j},S_{r}=S\) and \(f\) is such that \(f(u)=N(u)\) for all \(u\in X_{i}^{+}\).