# 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
Since \(T_{i}[b,\mathtt{P},f]\) is computed identically from some row in \(T_{j}\), let us say \((b,\mathtt{P}_{j},f_{j})\), it follows that \(T_{j}[b,\mathtt{P}_{j},f_{j}].\mathtt{Value}<\mathcal{C}_{f_{j}}(X_{j}^{+},S^{ \prime})\). This contradicts the premise that the table \(T_{i}\) is at the lowest height in the tree decomposition at which an entry is sub-optimal. Therefore, our premise is wrong. **Join node. ** We assume that \(S^{\prime}\) is indeed a better solution than \(S\) for the table entry \((b,\mathtt{P},f)\) of \(T_{i}\). Let \(S^{\prime}_{j}=S\cap(X_{j}^{+}\setminus X_{j})\) and \(S^{\prime}_{g}=S\cap(X_{g}^{+}\setminus X_{g})\). Let \(b^{\prime}_{j}=|S^{\prime}_{j}|\). Let \(\mathtt{P}^{\prime}_{j}=(A,C\cup R,L^{\prime}_{j},R^{\prime}_{j},B^{\prime}_{j})\) and \(\mathtt{P}^{\prime}_{g}=(A,C\cup L,L^{\prime}_{g},R^{\prime}_{g},B^{\prime}_{g})\) be the partitions of \(X_{j}\) and \(X_{g}\) defined using \(S^{\prime}_{j}\) and \(S^{\prime}_{g}\), respectively. Note that, \(L^{\prime}_{j}\cup R^{\prime}_{j}\cup B^{\prime}_{j}=L\cup B\) and \(L^{\prime}_{g}\cup R^{\prime}_{g}\cup B^{\prime}_{g}=R\cup B\). Let \(f^{\prime}_{j}\) be the SN function on \(X_{j}^{+}\) such that \(f^{\prime}_{j}(u)=f(u)\) for \(u\in A\cup C\cup L\cup B\) and \(f^{\prime}_{j}(u)=\emptyset\) for \(u\in R\). Let \(f^{\prime}_{g}\) be the SN function on \(X_{g}^{+}\) such that \(f^{\prime}_{g}(u)=f(u)\) for \(u\in A\cup C\cup R\), \(f^{\prime}_{g}(u)=\emptyset\) for \(u\in L\) and \(f^{\prime}_{g}(u)=f(u)\setminus S^{\prime}_{j}\). The coverage \(\mathcal{C}_{f}(X_{i}^{+},S^{\prime})\) can be written as \(\mathcal{C}_{f}(X_{i}^{+},S^{\prime})=\mathcal{C}_{f^{\prime}_{j}}(X_{j}^{+},S ^{\prime}_{j})+\mathcal{C}_{f^{\prime}_{g}}(X_{g}^{+},S^{\prime}_{g})-w(A)- \mathcal{C}_{f}(C,A)\), where the coverage of \(X_{j}^{+}\) by \(S^{\prime}_{j}\) and \(X_{g}^{+}\) by \(S^{\prime}_{g}\) are restricted to the partitions \(\mathtt{P}^{\prime}_{j}\) and \(\mathtt{P}^{\prime}_{g}\). We know that \(X_{i}=X_{j}=X_{g}\) in case of join node. The table entry \((b,\mathtt{P},f)\) is updated using the entries \((b_{j}+|A|,\mathtt{P}_{j},f_{j})\) and \((b-b_{j},\mathtt{P}_{g},f_{g})\) of the table \(T_{j}\) and \(T_{g}\), respectively. In other words, the values of variables \(b_{j},\mathtt{P}_{j},\mathtt{P}_{g},f_{j}\) and \(f_{g}\) are obtained from the Equation (2) described in the recursive definition of join node. The values \(b^{\prime}_{j},\mathtt{P}^{\prime}_{j},\mathtt{P}^{\prime}_{g},f^{\prime}_{j}\) and \(f^{\prime}_{g}\) are also feasible for the range given in the Equation (2). Then, we have \(T_{j}[b^{\prime}_{j}+|A|,\mathtt{P}^{\prime}_{j}f^{\prime}_{j}].\mathtt{Value }+T_{g}[b-b^{\prime}_{j},\mathtt{P}^{\prime}_{g},f^{\prime}_{g}].\mathtt{Value }+T_{g}[b-b^{\prime},\mathtt{P}_{g},f_{g}].\mathtt{Value}\). Since \(S^{\prime}\) is better than \(S\) for the entry \((b,\mathtt{P},f)\) of \(T_{i}\), we have \(T_{j}[b^{\prime}+|A|,\mathtt{P}_{j},f_{j}].\mathtt{Value}+T_{g}[b-b^{\prime}, \mathtt{P}_{g},f_{g}].\mathtt{Value}\). Since \(S^{\prime}\) is better than \(S\) for the entry \((b,\mathtt{P},f)\) of \(T_{i}\), we have \(T_{j}[b^{\prime}+|A|,\mathtt{P}_{j},f_{j}].\mathtt{Value}+T_{g}[b-b^{\prime}, \mathtt{P}_{g},f_{g}].\mathtt{Value}<\mathcal{C}_{f^{\prime}_{j}}(X_{j}^{+},S ^{\prime}_{j})+\mathcal{C}_{f^{\prime}_{g}}(X_{g}^{+},S^{\prime}_{g})\). The above inequality shows that at least one of the table entries \(T_{j}[b^{\prime}_{j}+|A|,\mathtt{P}^{\prime}_{j}f^{\prime}_{j}]\) or \(T_{g}[b-b^{\prime}_{j},\mathtt{P}^{\prime}_{g},f^{\prime}_{g}]\) is not optimal. This would again contradict the premise that \(i\) is the node at the least height at which some table entry is sub-optimal. This completes the case analysis and our proof. Hence the lemma. **Running Time. ** There are \(\mathcal{O}(n\;tw)\)-many nodes in the nice tree decomposition \(H\). Each node \(i\in H\) has a maximum of \((k+1)(5\cdot 2^{\Delta})^{tw}\) entries.