# 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
#### 5.3.2 Correctness and Running Time
There exists a \(Y\subseteq U\) of size \(\alpha(v)\) such that the probability \(\rho_{d}(\alpha,\beta,G_{i}^{\alpha,\beta},S)\) can be written as follows:  
\[\rho_{d}(\alpha,\beta,\mathcal{G}_{i}^{\alpha,\beta},S)=\rho_{d}(\alpha_{Y}, \beta^{\prime},\mathcal{G}_{j}^{\alpha_{Y},\beta^{\prime}},S_{j})\prod_{u\in Y }p(uv).\]The solution \(S_{j}\) is compatible for the row \(T_{j}[\alpha_{Y},\beta^{\prime}]\) where the vertices in \(Y\) are neighbors of \(v\) and degree constraint of these vertices is decreased by \(1\) in \(\alpha\) such that it will be satisfied by the edge from \(v\). Since \(W\) in the dynamic programming is optimal over all possible \(\alpha(v)\) sized subsets of \(W\), we have  
\[\rho_{d}(\alpha,\beta,\mathcal{G}_{i}^{\alpha,\beta},S) = \rho_{d}(\alpha_{Y},\beta^{\prime},G_{j}^{\alpha_{Y},\beta^{ \prime}},S_{j})\prod_{u\in Y}p(uv)\leq\rho_{d}(\alpha_{W},\beta^{\prime}, \mathcal{G}_{j}^{\alpha_{W},\beta^{\prime}},T_{j}[\alpha_{W},\beta^{\prime}]. \texttt{Solution})\prod_{u\in W}p(uv)\] \[\leq T_{j}[\alpha_{W},\beta^{\prime}].\texttt{Value}\prod_{u\in W}p( uv)=T_{i}[\alpha,\beta].\texttt{Value}.\]  
This completes the argument of the case when \(i\) is an introduce node. **When \(i\) is a forget node. ** Let \(j\) be the child of \(i\), and \(X_{i}=X_{j}\setminus\{v\}\) for some \(v\in X_{j}\). We consider two cases depending on whether \(v\) belongs to \(S\). We first consider the case when \(v\
otin S\). Consider the functions \(\alpha_{0,\emptyset}\) and \(\beta_{0,\emptyset}\) as defined in the recursive computation of forget node. Since \(v\
otin S\), \(v\) will get zero degree constraint in both functions \(\alpha\) and \(\beta\), and other vertices will have same constraints as \(\alpha\) and \(\beta\) values. Then, the probability \(\rho_{d}(\alpha,\beta,G_{i}^{\alpha,\beta},S)\) can be written as follows:  
\[\rho_{d}(\alpha,\beta,G_{i}^{\alpha,\beta},S)=\rho_{d}(\alpha_{0,\emptyset}, \beta_{0,\emptyset},G_{j}^{\alpha_{0,\emptyset},\beta_{0,\emptyset}},S).\]  
Since \(j\) is a node at height \(h-1\), we have  
\[\rho_{d}(\alpha,\beta,G_{i}^{\alpha,\beta},S) = \rho_{d}(\alpha_{0,\emptyset},\beta_{0,\emptyset},G_{j}^{\alpha_ {0,\emptyset},\beta_{0,\emptyset}},S)\leq T_{j}[\alpha_{0,\emptyset},\beta_{0, \emptyset}].\texttt{Value}\] \[S_{\alpha,\beta}=T_{i}[\alpha,\beta].\texttt{Solution}=T_{j}[\alpha^{\prime}, \beta^{\prime}].\texttt{Solution}\]0  
Secondly, we consider the case when \(v\in S\). Let \(U=(N(v)\cap X_{j})\setminus\alpha^{-1}(0)\). Since \(v\) is in \(X_{j}\) but \(v\) is not in its parent node \(X_{i}\), \(v\) should have degree \(d\) in the \((\alpha,\beta)\)-constrained Probabilistic-Core problem. Then, \(\alpha(v)=a\) and \(\beta(v)=d-a\) for an \(0\leq a\leq d\). Let \(Y\subseteq U\) of size \(a\) be the set of vertices that have an edge to \(v\) to compensate the degree constraint \(\alpha(v)\) at \(v\). Then, each vertex \(u\in Y\) will gain a degree constraint \(\alpha(u)\) and lose a degree constraint \(\beta(u)\). Using the integer \(a\) and the set \(Y\), the probability \(\rho_{d}(\alpha,\beta,\mathcal{G}_{i}^{\alpha,\beta},S)\) can be written as follows:  
\[S_{\alpha,\beta}=T_{i}[\alpha,\beta].\texttt{Solution}=T_{j}[\alpha^{\prime}, \beta^{\prime}].\texttt{Solution}\]1  
Since \(j\) is a node at height \(h-1\), we know that the row \(T_{j}[\alpha_{a,Y},\beta_{a,Y}]\) is computed optimally. That is,  
\[S_{\alpha,\beta}=T_{i}[\alpha,\beta].\texttt{Solution}=T_{j}[\alpha^{\prime}, \beta^{\prime}].\texttt{Solution}\]2  
This completes the argument of the case when \(i\) is a forget node. **When \(i\) is a join node. ** Let \(j\) and \(g\) be the children of \(i\), and \(X_{i}=X_{j}=X_{g}\). The set \(S\setminus X_{i}\) can be partitioned into sets \(S_{j}\) and \(S_{g}\) where \(S_{j}=(S\setminus X_{i})\cap X_{j}\) and \(S_{g}=(S\setminus X_{i})\cap X_{g}\). Let \(U=\{u\in X_{i}\mid\alpha(v)>0\}\) and \(S_{i}=X_{i}\setminus\alpha^{-1}(0)\).