# 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
We consider the following five-way partitions of \(X_{j}\). * \(\mathtt{P}_{1}=(A\cup\{v\},C,L,R,B)\)
* \(\mathtt{P}_{2}=(A,C\cup\{v\},L,R,B)\)
* \(\mathtt{P}_{3}=(A,C,L\cup\{v\},R,B)\)
* \(\mathtt{P}_{4}=(A,C,L,R\cup\{v\},B)\)
* \(\mathtt{P}_{5}=(A,C,L,R,B\cup\{v\})\)  
Let \(f_{j}\) be the SN-function defined as follows: for \(u\in X_{i}\), \(f_{j}(u)=f(u)\) and \(f_{j}(v)=N(v)\). Let \(\mathtt{P}_{j}=\underset{\mathtt{P}^{\prime}\in\{\mathtt{P}_{i}\}_{i=1}^{5}}{ \arg\max}T_{j}[b,\mathtt{P}^{\prime},f_{j}].\mathtt{Value}\). \(T_{i}[b,\mathtt{P},f]\) is defined as follows:  
\[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}\]  
**Join node. ** Let \(i\) be a join node with children \(j\) and \(g\) such that \(X_{i}=X_{j}=X_{g}\). 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. We consider the sets \(\mathcal{U}_{j}\) and \(\mathcal{U}_{g}\) of all SN-functions defined on \(X_{j}^{+}\) and \(X_{g}^{+}\), respectively, satisfying the following conditions:  
* For each \(v\in L\), \(f_{j}(v)=f(v)\) and \(f_{g}(v)=\emptyset\). * For each \(v\in R\), \(f_{j}(v)=\emptyset\) and \(f_{g}(v)=f(v)\). * For each \(v\in B\), \(f_{j}(v)\) and \(f_{g}(v)\) are defined as follows. For each partition \(f_{1}(v)\cup f_{2}(v)=f(v)\cap X_{i}^{+}\), \(f_{j}(v)=f_{1}(v)\cup(f(v)\setminus X_{i}^{+})\) and \(f_{g}(v)=f_{2}(v)\cup(f(v)\setminus X_{i}^{+})\). We then consider all possible candidates for \(L_{j},R_{j},B_{j}\) such that \(L_{i}\cup R_{j}\cup B_{j}=L\cup B\) and \(L_{g},R_{g},B_{g}\) such that \(L_{g}\cup R_{g}\cup B_{g}=R\cup B\). Each such candidate defines a \(\mathtt{P}^{\prime}_{j}=(A,C\cup R,L_{j},R_{j},B_{j})\) of \(X_{j}\) and a \(\mathtt{P}^{\prime}_{g}=(A,C\cup L,L_{g},R_{g},B_{g})\) of \(X_{g}\). Let \(\mathcal{R}_{j}\) and \(\mathcal{R}_{g}\) denote the set of all such candidate partitions of \(X_{j}\) and \(X_{g}\), respectively. Let \(\mathtt{P}_{j}\in\mathcal{R}_{j}\), \(\mathtt{P}_{g}\in\mathcal{R}_{g}\), \(f_{j}\in\mathcal{U}_{j}\), \(f_{g}\in\mathcal{U}_{g}\) and \(0\leq b^{\prime}\leq b-|A|\) be the values at which the maximum value for Equation (2) is achieved. \[\max_{ \begin{subarray}{c}0\leq b_{j}\leq b-|A|\\ \mathtt{P}^{\prime}_{j}\in\mathcal{R}_{j},\mathtt{P}^{\prime}_{g}\in\mathcal{ R}_{g}\\ \tilde{f}^{\prime}_{j}\in\mathcal{U}_{j},f^{\prime}_{g}\in\mathcal{U}_{g}\end{subarray} }T_{j}[ b_{j}+|A|,\mathtt{P}^{\prime}_{j},f^{\prime}_{j}].\texttt{Value}+T_{g}[b-b_{j}, \mathtt{P}^{\prime}_{g},f^{\prime}_{g}].\texttt{Value}. \tag{2}\]  
The value of the row corresponding to \((b,\mathtt{P},f)\) in \(T_{i}\) is given as follows:  
\[T_{i}[b,\mathtt{P},f].\texttt{Solution} = T_{j}[b^{\prime}+|A|,\mathtt{P}_{j},f_{j}].\texttt{Solution}\cup T _{g}[b-b^{\prime},\mathtt{P}_{g},f_{g}].\texttt{Solution}\] \[T_{i}[b,\mathtt{P},f].\texttt{Value} = T_{j}[b^{\prime}+|A|,\mathtt{P}_{j},f_{j}].\texttt{Value}+T_{g}[ b-b^{\prime},\mathtt{P}_{g},f_{g}].\texttt{Value}-\mathcal{C}_{f}(A\cup C,A).\]  
We now prove that the update steps presented above are correct. Lemma 5: _For each node \(i\in H\), for each row \((b,\mathtt{P},f)\) in \(T_{i}\), the pair \(T_{i}[b,\mathtt{P},f].\texttt{Solution}\), \(T_{i}[b,\mathtt{P},f].\texttt{Value}\) is such that \(\mathcal{C}(X_{i}^{+},T_{i}[b,\mathtt{P},f].\texttt{Solution})=T_{i}[b,\mathtt{ P},f].\texttt{Value}\), and this is the maximum possible value._  
Proof: The proof is by induction on the height of a node in \(H\). The height of a node \(i\) in a rooted tree \(H\) is the distance to the farthest leaf in the subtree rooted at \(i\). The base case is when \(i\) is a leaf node in \(H\), and clearly its height is \(0\). For a leaf node \(i\) with \(X_{i}=\emptyset\), the row with \(b=0\), \(\mathtt{P}=(\emptyset,\emptyset,\emptyset,\emptyset,\emptyset)\) and \(f:\emptyset\rightarrow\emptyset\) is the only valid row entry and its value is \(0\).