# 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  
**Lemma 7**. : _Let \(i\) be a node in \(\mathcal{T}\). For every pair of functions \(\alpha,\beta:X_{i}\rightarrow\{0,1,\ldots,d\}\), the row \(T_{i}[\alpha,\beta]\) is computed optimally._  
Proof. : Let \(i\) be a node in \(\mathcal{T}\). We claim that for each pair of functions \(\alpha,\beta:X_{i}\rightarrow\{0,1,\ldots,d\}\), the row \(T_{i}[\alpha,\beta]\) computes the optimal solution for the instance \(\mathcal{G}_{i}^{\alpha,\beta}\) of the \((\alpha,\beta)\)-constrained Probabilistic-Core problem. That is, the set \(S_{\alpha,\beta}=T_{i}[\alpha,\beta].\texttt{Solution}\) is an optimal solution for the above instance. Let \(A=X_{i}\setminus(\alpha^{-1}(0)\cap\beta^{-1}(0))\). We show that for any \(S=A\cup Z\) for some \(Z\subseteq X_{i}^{+}\setminus X_{i}\),  
\[\rho_{d}(\alpha,\beta,\mathcal{G}_{i}^{\alpha,\beta},S)\leq\rho_{d}(\alpha, \beta,\mathcal{G}_{i}^{\alpha,\beta},S_{\alpha,\beta}).\]  
The proof is by induction on the height of a node in \(\mathcal{T}\). The height of a node \(i\) in the rooted tree \(\mathcal{T}\) is the distance to the farthest leaf in the subtree rooted at \(i\). The base case is when \(i\) is a leaf node in \(\mathcal{T}\) and height is \(0\). For a leaf node \(i\) with \(X_{i}=\emptyset\), the row with \(\alpha,\beta:\emptyset\rightarrow\{0,1,\ldots d\}\) completes the proof of the base case. Let us assume that the claim is true for all nodes of height at most \(h-1\geq 0\). We now prove that if the claim is true at all nodes of height at most \(h-1\), then it is true for a node of height \(h\). Let \(i\) be a node of height \(h\). Clearly \(i\) is not a leaf node. **When \(i\) is an introduce node. ** Let \(j\) be the child of \(i\), and \(X_{i}=X_{j}\cup\{v\}\) for some \(v\
otin X_{j}\). If \(\beta(v)>0\), then no feasible solution exists since \(N(v)\cap(X_{i}^{+}\setminus X_{i})=\emptyset\). This is captured in our dynamic programming. In the further cases, we consider \(\beta(v)=0\). Let \(L=N(v)\cap X_{i}\). Consider the case when \(\alpha(v)=0\). That is, the vertex \(v\) is not part of the solution. The recursive definition of the dynamic programming gives  
\[S_{\alpha,\beta}=T_{i}[\alpha,\beta].\texttt{Solution}=T_{j}[\alpha^{\prime}, \beta^{\prime}].\texttt{Solution}\]  
where \(\alpha^{\prime}\) and \(\beta^{\prime}\) are as defined in the dynamic programming. A feasible solution to the row \(T_{i}[\alpha,\beta]\) should be feasible for the row \(T_{j}[\alpha^{\prime},\beta^{\prime}]\). Otherwise, the degree constraints are not met by the solution. For the solution \(S=A\cup Z\),  
\[\rho_{d}(\alpha^{\prime},\beta^{\prime},\mathcal{G}_{j}^{\alpha^{\prime},\beta ^{\prime}},S)\leq\rho_{d}(\alpha^{\prime},\beta^{\prime},\mathcal{G}_{j}^{ \alpha^{\prime},\beta^{\prime}},S_{\alpha,\beta})\]  
since \(j\) is a node at height \(h-1\) and by our induction hypothesis. Also,  
\[\rho_{d}(\alpha^{\prime},\beta^{\prime},\mathcal{G}_{j}^{\alpha^{\prime},\beta ^{\prime}},S)=\rho_{d}(\alpha,\beta,\mathcal{G}_{i}^{\alpha,\beta},S)\]  
since \(v\
otin S\). Then, we have  
\[\rho_{d}(\alpha,\beta,\mathcal{G}_{i}^{\alpha,\beta},S) = \rho_{d}(\alpha^{\prime},\beta^{\prime},\mathcal{G}_{j}^{\alpha^{ \prime},\beta^{\prime}},S)\leq\rho_{d}(\alpha^{\prime},\beta^{\prime}, \mathcal{G}_{j}^{\alpha^{\prime},\beta^{\prime}},S_{\alpha,\beta})=\rho_{d}( \alpha,\beta,\mathcal{G}_{i}^{\alpha,\beta},S_{\alpha,\beta}).\]  
This completes the case when \(\beta(v)=0\) and \(\alpha(v)=0\). Now we consider the case where \(\alpha(v)>0\). In the solution \(S=A\cup Z\), we need \(\alpha(v)\) neighbors of \(U\) in the \(d\)-core where the set \(U=(N(v)\cap X_{i})\setminus(\alpha^{-1}(0)\cap\beta^{-1}(0))\). Let \(S_{j}=S\setminus\{v\}\).