# 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  
We show that the Probabilistic-Core-RF problem admits an FPT algorithm with treewidth as the parameter. The input consists of an instance \(\langle\mathcal{G}=(V,E,p),d\rangle\) of the Probabilistic-Core-RF problem. A nice tree decomposition \((X,\mathcal{T})\) of the graph \(G=(V,E)\) is also given as part of the input.  
Let \(i\) be any node in \(\mathcal{T}\) and \(\alpha:X_{i}\rightarrow\{0,1,\ldots,d\}\) and \(\beta:X_{i}\rightarrow\{0,1,\ldots,d\}\) be a pair of functions on \(X_{i}\). Given a set \(K\subseteq V\), the set \(K\) is said to be \((\alpha,\beta)\)-constrained \(d\)-core of \(G\) if  
1. for each \(v\in X_{i}\cap K\), \(|N(v)\cap K|=\alpha(v)+\beta(v)\) and \(|N(v)\cap K\cap X_{i}|=\alpha(v)\), and
2. for each \(v\in K\setminus X_{i}\), \(|N(v)\cap K|=d\).  
Let \(\mathcal{G}_{i}^{\alpha,\beta}\) denote the uncertain graph \(\mathcal{G}[X_{i}^{+}\setminus(\alpha^{-1}(0)\cap\beta^{-1}(0))]\). We define a constrained version of the Probabilistic-Core-RF problem as follows. Given a set \(K\), the probability that the set \(K\) is an \((\alpha,\beta)\)-constrained \(d\)-core in \(\mathcal{G}_{i}^{\alpha,\beta}\) is given by:  
\[\rho_{d}(\alpha,\beta,\mathcal{G}_{i}^{\alpha,\beta},K)=\sum_{H\subseteq \mathcal{G}_{i}^{\alpha,\beta}}P(H)I^{\prime}(H,\alpha,\beta,K,d),\]  
where \(I^{\prime}(H,\alpha,\beta,K,d)\) is an indicator function that takes value \(1\) if and only if \(K\) is an \((\alpha,\beta)\)-constrained \(d\)-core of \(H\). The optimization version of the \((\alpha,\beta)\)-constrained Probabilistic-Core-RF problem seeks to find the set \(K\) such that \(\rho_{d}(\alpha,\beta,\mathcal{G}_{i}^{\alpha,\beta},K)\) is maximized. The solution for \((\alpha,\beta)\)-constrained Probabilistic-Core-RF problem for different values of \(i\), \(\alpha\) and \(\beta\) on \(\mathcal{G}\) are partial solutions which are used to come up with a recursive specification of the optimum value. The dynamic programming (DP) formulation on the nice tree decomposition \((X,\mathcal{T})\) results in an FPT algorithm with treewidth as the parameter.  
The dynamic programming formulation maintains a table \(T_{i}\) at every node \(i\in X\). Each row in the table \(T_{i}\) is a pair of functions \(\alpha\) and \(\beta\) such that \(\alpha,\beta:X_{i}\rightarrow\{0,1,\ldots,d\}\). The column corresponding to the row \((\alpha,\beta)\) is a pair (Solution,Value) which consists of a set \(S_{\alpha,\beta}\) and a probability value. Further, the set \(S_{\alpha,\beta}\) is an optimal solution for the \((\alpha,\beta)\)-constrained Probabilistic-Core-RF problem on the instance \(\langle\mathcal{G}_{i}^{\alpha,\beta},d\rangle\).  
Intuitively, the functions \(\alpha\) and \(\beta\) defined on \(X_{i}\) stand for the \"in-bag-degree\" and \"out-bag-degree\" constraints, respectively, for each vertex \(v\in X_{i}\). We maintain the candidate solutions in the table for different values of the functions \(\alpha\) and \(\beta\). We allow the candidate solutions that are infeasible at current stage and those vertices which are not satisfied with degree \(d\) will get neighbors from nodes at a higher level in the tree decomposition. The optimal solution for the instance \(\langle\mathcal{G},d\rangle\) of the Probabilistic-Core-RF problem can be obtained from the table \(T_{r}\) where \(r\) is the root of the tree decomposition \(\mathcal{T}\).