# Parameterized Optimization in Uncertain Graphs--A Survey and Some Results
## 5 Parameterized Complexity of Probabilistic-Core Problem
### The Probabilistic-Core-RF Problem is FPT by Treewidth
#### Dynamic Programming  
We now present the dynamic programming formulation on the different types of nodes in \(\mathcal{T}\). Let \(i\in\mathcal{T}\) be a node with bag \(X_{i}\). For a pair of functions \(\alpha,\beta:X_{i}\rightarrow\{0,1,\ldots,d\}\), we show how to compute the table entry \(T_{i}[\alpha,\beta]\) in each type of node as follows. **Leaf node. ** Let \(i\) be a leaf node with bag \(X_{i}=\emptyset\). We have one row in the table \(T_{i}\). Let \(\alpha,\beta:\emptyset\rightarrow\{0\}\) be the pair of functions corresponding to the row and the value of the table entry is given as:  
\[T_{i}[\alpha,\beta]=(\emptyset,0.0).\]  
**Insert node. ** Let \(i\) be an insert node with a child \(j\), and let \(X_{i}=X_{j}\cup\{v\}\) for some \(v\
otin X_{j}\). The row \(T_{i}[\alpha,\beta]\) is computed based on the value of \(\alpha(v)\) and \(\beta(v)\). If \(\beta(v)>0\), then the row \(T_{i}[\alpha,\beta]\) becomes infeasible since \(N(v)\cap X_{i}^{+}\subseteq X_{i}\). That is,  
\[T_{i}[\alpha,\beta]=(\emptyset,0.0).\]  
In the rest of the cases we have \(\beta(v)=0\). We define \(\beta^{\prime}:X_{j}\rightarrow\{0,1,\ldots,d\}\) to be a function such that \(\beta^{\prime}(u)=\beta(u)\) for all \(u\in X_{j}\). When \(\alpha(v)=0\), then the vertex \(v\) will not be in the solution \(S_{\alpha,\beta}\). Let \(\alpha^{\prime}:X_{j}\rightarrow\{0,1,\ldots,d\}\) be a function such that \(\alpha^{\prime}(u)=\alpha(u)\) for all \(u\in X_{j}\). The value of the row \(T_{i}[\alpha,\beta]\) is same as \(T_{j}[\alpha^{\prime},\beta^{\prime}]\) since \(v\) is excluded. When \(\alpha(v)>0\), then \(v\) is part of \(S_{\alpha,\beta}\)Let \(U=(N(v)\cap X_{i})\setminus\alpha^{-1}(0)\). Then, we have \(|U|\geq\alpha(v)\). Otherwise, no feasible solution exists for the row \(T_{i}[\alpha,\beta]\). That is, degree constraint of \(v\) will not be met in any feasible solution. Assume \(|U|\geq\alpha(v)\). Let \(Y\subseteq U\) be a subset of \(U\) of size \(\alpha(v)\), and \(q(v,Y)=\prod_{u\in Y}p(uv)\). The vertices in \(Y\) that are the neighbors of \(v\) contribute degree \(\alpha(v)\) to \(v\). Then, each vertex \(u\in Y\) will lose a degree from \(\alpha(u)\) in the node \(j\). Define \(\alpha_{Y}:X_{j}\to\{0,1,\ldots,d\}\) to be  
\[\alpha_{Y}(u)= \begin{cases}\alpha(u)&\text{if }u\
otin Y\\ \alpha(u)-1&\text{if }u\in Y.\end{cases} \]  
Let  
\[W=\operatorname*{arg\,max}_{Y\subseteq U,|Y|=\alpha(v)}q(v,Y)T_{j}[\alpha_{Y},\beta^{\prime}].\texttt{Value}\]  
be the best \(\alpha(v)\) neighbors of \(v\) such that the solution obtained from the table \(T_{j}\) is maximized. Then, the recursive definition of the row \(T_{i}[\alpha,\beta]\) is given as,  
\[T_{i}[\alpha,\beta]=(T_{j}[\alpha_{W},\beta^{\prime}].\texttt{Solution}\cup \{v\},q(v,W)T_{j}[\alpha_{W},\beta^{\prime}].\texttt{Value}).\]  
**Forget node. ** Let \(i\) be a forget node with a child \(j\), and let \(X_{i}=X_{j}\setminus\{v\}\) for some \(v\in X_{j}\). From the definition of the tree decomposition, it follows that \(N(v)\subseteq X_{j}^{+}\). Since \(N(v)\subseteq X_{j}^{+}\), either \(v\) is part of solution with constraint \(\alpha(v)+\beta(v)=d\) or \(v\) is not part of solution. Let \(U=(N(v)\cap X_{j})\setminus\alpha^{-1}(0)\). For each \(0\leq a\leq\min(d,|U|)\) and \(Y\subseteq U\) of size \(a\), we define \(\alpha_{a,Y},\beta_{a,Y}:X_{j}\to\{0,1,\ldots,d\}\) such that  
\[\alpha_{a,Y}(u)=\begin{cases}\alpha(u)&\text{if }u\
eq v\text{ and }u\
otin Y\\ \alpha(u)+1&\text{if }u\
and  
\[\beta_{a,Y}(u)= \begin{cases}\beta(u)&\text{if }u\
eq v\text{ and }u\
otin Y\\ \beta(u)-1&\text{if }u\
eq v\text{ and }u\in Y\\ d-a&\text{if }u=v,\end{cases} \]  
For \(0\leq a\leq min(d,|U|)\), let  
\[\alpha_{a},\beta_{a}=\operatorname*{arg\,max}_{\alpha_{a,Y},\beta_{a,Y}:Y \subseteq U,|Y|=a}T_{j}[\alpha_{a,Y},\beta_{a,Y}].\texttt{Value}.\]  
Let \(t=\operatorname*{arg\,max}_{0\leq a\leq min(d,|U|)}T_{j}[\alpha_{a},\beta_{a}]. \texttt{Value}\). Then the value of the row \(T_{i}[\alpha,\beta]\) is equal to \(T_{j}[\alpha_{t},\beta_{t}]\). **Join node.