# 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}\))
### Bottom-Up Computation of an Optimal Set  
For each node \(i\in H\), we associate a table \(T_{i}\). Each row in the table \(T_{i}\) is a triple which consists of an integer \(b\), a five way partitioning \(\mathtt{P}=(A,C,L,R,B)\) of \(X_{i}\) and an SN-function \(f\) defined on \(X_{i}^{+}\). Throughout this section we assume that for vertices \(u\in X_{i}^{+}\setminus X_{i}\), \(f(u)=N(u)\). The columns corresponding to a row \((b,\mathtt{P},f)\) is a vertex set \(T_{i}[b,\mathtt{P},f]\).Solution and a value \(T_{i}[b,\mathtt{P},f]\).Value. Let \(S\) denote \(T_{i}[b,\mathtt{P},f]\).Solution. To define the value \(T_{i}[b,\mathtt{P},f]\).Value associated with \(S\), consider \(Z=S\setminus A\), and let \(Z_{j}=Z\cap(X_{j}^{+}\setminus X_{j})\) and \(Z_{g}=Z\cap(X_{g}^{+}\setminus X_{g})\). Then, \(T_{i}[b,\mathtt{P},f]\).Value\(=w(A)+\mathcal{C}_{f}(C,A)+\mathcal{C}_{f}(L,A\cup Z_{j})+\mathcal{C}_{f}(R,A\cup Z _{g})+\mathcal{C}_{f}(B,A\cup Z)+\mathcal{C}(X_{i}^{+}\setminus X_{i},S)\). The set \(T_{i}[b,\mathtt{P},f]\).Solution is a set \(S\) of size \(b\) such that \(S\cap X_{i}=A\) and the associated value \(T_{i}[b,\mathtt{P},f]\).Value is maximized. **Leaf node. ** Let \(i\in H\) be a leaf node with bag \(X_{i}=\emptyset\). The only possible five-way partition of an empty set is the set with five empty sets and the budget is \(b=0\). The only valid SN-function is \(f:\emptyset\rightarrow\emptyset\). Therefore, the value of the corresponding row in the table is  
\[T_{i}[b,\mathtt{P},f]=\{\mathtt{Solution}=\emptyset,\mathtt{Value}=0\}\text{ for }b=0,\mathtt{P}=(\emptyset,\emptyset,\emptyset,\emptyset, \emptyset)\text{ and }f:\emptyset\rightarrow\emptyset.\]  
It is clear that the empty set is the set that achieves the maximum for the Max-Exp-Cover-1-RF problem on the empty graph with budget \(b=0\). Therefore, at the leaf nodes in \(H\), the table \(T_{i}\) maintains the optimum solution for each row. The time to update an entry is \(\mathcal{O}(1)\). **Introduce node. ** Let \(i\) be an introduce node with child \(j\) such that \(X_{i}=X_{j}\cup\{v\}\) for some \(v\
ot\in X_{j}\). Let \(0\leq b\leq k\) be an integer, \(\mathtt{P}=(A,C,L,R,B)\) be a five-way partition of \(X_{i}\) and \(f\) be the SN-function defined on \(X_{i}^{+}\). The computation of the table entry is split into two cases, depending on whether the vertex \(v\) belongs to the set \(A\) in the partition \(\mathtt{P}\) or not. 1. **Case \(v\in A\). ** Define \(C_{v}=\{u\in X_{i}\setminus A\mid v\in N(u)\cap f(u)\}\). Let \(\mathtt{P}_{j}\) denote the partition of \(X_{j}\) obtained by removing vertex \(v\) from the set \(A\) of the partition \(\mathtt{P}\). Let \(f_{j}:X_{j}\to 2^{V}\) be the SN-function defined as follows: \[f_{j}(u)= \begin{cases}f(u)\setminus\{v\}&\text{ if }u\in C_{v}\\ f(u)&\text{ otherwise.}\end{cases} \] Then, \[T_{i}[b,\mathtt{P},f].\mathtt{Solution} = T_{j}[b-1,\mathtt{P}_{j},f_{j}].\mathtt{Solution}\cup\{v\}\] \[T_{i}[b,\mathtt{P},f].\mathtt{Value} = T_{j}[b-1,\mathtt{P}_{j},f_{j}].\mathtt{Value}+w(v)+\mathcal{C}_{ f}(C_{v},v)\]
2. **Case \(v\
ot\in A\). ** Since \(v\) is in \(X_{i}\) but not in \(X_{j}\) it follows that \(N(v)\cap X_{i}^{+}\subseteq X_{i}\). Therefore, the coverage of the vertex \(v\) by the vertices that occur only in \(X_{j}^{+}\setminus X_{j}\) is zero. Let \(\mathtt{P}_{j}\) be the partition of \(X_{j}\) obtained by removing the vertex \(v\) from the appropriate set in the partition \(\mathtt{P}\). The SN-function \(f_{j}\) is defined as follows on the set \(X_{j}^{+}\): For \(u\in X_{i}\setminus\{v\}\), \(f_{j}(u)=f(u)\). \[T_{i}[b,\mathtt{P},f].\mathtt{Solution} = T_{j}[b,\mathtt{P}_{j},f_{j}].\mathtt{Solution}\] \[T_{i}[b,\mathtt{P},f].\mathtt{Value} = T_{j}[b,\mathtt{P}_{j},f_{j}].\mathtt{Value}+\mathcal{C}_{f}(v,A)\]  
**Forget node. ** Let \(i\) be a forget node with child \(j\) such that \(X_{i}=X_{j}\setminus\{v\}\) for some \(v\in X_{j}\). Let \(0\leq b\leq k\) be a budget, \(\mathtt{P}=(A,C,L,R,B)\) be a five-way partition of \(X_{i}\) and \(f\) be an SN-function.