# 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
The functions \(\beta_{x}\) and \(\beta^{\prime}_{x}\) for the given function \(x\) are defined in the description of dynamic programming. Since both \(j\) and \(g\) are nodes at height at most \(h-1\), by induction hypothesis, the rows \(T_{j}[\alpha_{j},\beta_{x}]\) and \(T_{g}[\alpha^{\prime},\beta^{\prime}_{x}]\) are computed optimally. Therefore, we have  
\[S_{\alpha,\beta}=T_{i}[\alpha,\beta].\texttt{Solution}=T_{j}[\alpha^{\prime}, \beta^{\prime}].\texttt{Solution}\]3 \[S_{\alpha,\beta}=T_{i}[\alpha,\beta].\texttt{Solution}=T_{j}[\alpha^{\prime}, \beta^{\prime}].\texttt{Solution}\]4 \[S_{\alpha,\beta}=T_{i}[\alpha,\beta].\texttt{Solution}=T_{j}[\alpha^{\prime}, \beta^{\prime}].\texttt{Solution}\]5  
where \(y\) is the optimal distribution of the degree which results in the \(T_{i}[\alpha,\beta].\mathtt{Value}\), as defined in the recursive formulation at a join node. This completes the argument for the case when \(i\) is a join node. Hence the lemma. For a possible world \(H\sqsubseteq\mathcal{G}\), the degree of a vertex \(v\in V(H)\) is at most the degree of \(v\) in \(G=(V,E)\). A vertex with degree less than \(d\) in \(G\) cannot be an element of a core in any possible world. Thus, those vertices can be excluded throughout the algorithm. Such a pruning results in either the pruned graph being an empty graph or the minimum degree of the pruned graph is becoming at least \(d\). We state the following Lemma from [PERSON] et al. (2018). **Lemma 8** ([PERSON] et al (2018)). : _For a graph \(G=(V,E)\) with \(|V|\geq 2\), \(\delta(G)\leq tw(G)\)._  
In the following lemma, we analyze the running time of the dynamic programming algorithm. **Lemma 9**. : _The Probabilistic-Core-RF problem can be solved optimally in time \(2^{\mathcal{O}(tw\log tw)}n^{\mathcal{O}(1)}\)._  
Proof. : For each node \(i\) in \(\mathcal{T}\), our dynamic programming generates a table \(T_{i}\) with \((d+1)^{2 tw}=\mathcal{O}(d^{2 tw})\) rows. Each row \(T_{i}[\alpha,\beta]\) for some \(\alpha,\beta:X_{i}\rightarrow\{0,1,\ldots,d\}\) is computed in our dynamic programming based on the type of node \(i\). When \(i\) is leaf node, a single row exists in \(T_{i}\) and that is computed in \(\mathcal{O}(1)\) time. When \(i\) is introduce node, we consider two cases that \(\alpha(v)=0\) and \(\alpha(v)>0\). If \(\alpha(v)=0\), then the functions \(\alpha_{j}\) and \(\beta_{j}\) can be computed in time \(\mathcal{O}(tw)\). If \(\alpha(v)>0\), the set \(U^{\prime}\) can be found by enumerating all \(\alpha(v)\) sized sets in \(U\). This will take \(\mathcal{O}(|Y|^{\beta(v)})\) time and using the upper bound on values we get \(\mathcal{O}(tw^{d})\). It follows that if \(i\) is an introduce node, then \(T_{i}[\alpha,\beta]\) can be computed in time \(\mathcal{O}(tw^{d})\). When \(i\) is a forget node, for each value of \(0\leq a\leq min(d,|U|)\), we enumerate all \(a\) sized subsets of \(Y\). This requires \(\mathcal{O}(tw^{k}k)\) time. When \(i\) is join node, we need to compute the optimal distribution of \(\beta(v)\) for each vertex \(v\in X_{i}\). This requires \(\mathcal{O}(d^{tw})\) time. From Lemma 8, we know that \(d\leq tw\), we upper bound the value \(d\) by \(tw\). Overall, a row \(T_{i}[\alpha,\beta]\) can be computed in time \(\mathcal{O}(tw^{tw})\). The entire table \(T_{i}\) can be computed in time \(\mathcal{O}(tw^{3 tw})=2^{\mathcal{O}(tw\log tw)}\). The nice tree decomposition \((X,\mathcal{T})\) has \(\mathcal{O}(n\cdot tw)\) many nodes and a table on each node can be computed in time \(\mathcal{O}(2^{\mathcal{O}(tw\log tw)})n^{\mathcal{O}(1)}\). An optimal solution to the Probabilistic-Core-RF problem on the input uncertain graph \(\mathcal{G}\) will be obtained from the table of the root node \(r\). That is, \(T_{r}[\alpha:\mathcal{O}\rightarrow\{0\},\beta:\mathcal{O}\rightarrow\{0\}]. \mathtt{Solution}\) is the optimal solution. The preceding lemmas results in the following theorem. Theorem 3.: _The Probabilistic-Core problem admits an FPT algorithm for the parameter \(tw\)._