# Parameterized Optimization in Uncertain Graphs--A Survey and Some Results
## 5 Parameterized Complexity of Probabilistic-Core Problem
### An Exact Algorithm for the Probabilistic-Core-LRO Problem  
We present a polynomial time algorithm (see as Algorithm 1) for the Probabilistic-Core-LRO problem. Let \(\langle\mathcal{G}=(V,E,p),d\rangle\) be an instance of the Probabilistic-Core-LRO problem. As per the definition of the LRO model, let the set \(\{G_{0},\ldots,G_{m}\}\) be the possible worlds of \(\mathcal{G}\), where \(G_{0}=(V,\emptyset)\) and for \(0\leq i\leq m-1\), \(E(G_{i+1})=E(G_{i})\cup\{e_{i}\}\). For each \(0\leq i\leq m-1\), we consider the linear order in which \(G_{i}\) precedes \(G_{i+1}\).  
```
Data:\(\mathcal{G}=(V,E,p)\), \(d\) Result: A set \(C\subseteq V\) with a probability \(q\). for\(i\gets 0\) to \(m\)do \(C\gets V\); while\(\delta(G_{i}[C])<d\)do  Let \(v\) be a vertex such that \(deg_{G_{i}[C]}(v)<d\); \(C\gets C\setminus\{v\}\) ;  end for if\(C\
eq\emptyset\)then return\(C,p(e_{i})\);  end if  end for return\(\emptyset,0.0\);
```  
**Algorithm 1**Probabilistic-Core-LRO  
**Lemma 6**: _The Algorithm 1 solves the Probabilistic-Core-LRO problem in polynomial time._  
Proof: By definition of the possible worlds, \(G_{m}=(V,E)\). If \(\delta(G_{m})<d\), then \(G_{m}\) does not contain a \(d\)-core. Moreover, for \(0\leq i<m\), since \(G_{i}\) is an edge subgraph of \(G_{m}\), no graph in the possible worlds has a \(d\)-core. This is indicated by the return value-pair of the \(\emptyset\) and probability \(0.0\). On the other hand if \(\delta(G_{m})\geq d\), let \(G_{i}\) be the first graph in the linear ordering of possible worlds for which a non-empty \(C\) is computed by Algorithm 1 on exit from the While-loop. Clearly, \(C\) induces a \(d\)-core in \(G_{i}\). Since \(G_{i}\) is the first graph which contains a \(d\)-core, for each \(0\leq j\leq i-1\), \(G_{j}\) does not contain a \(d\)-core. Further, for every \(j>i\), \(C\) is a \(d\)-core in \(G_{j}\) since it is an edge-subgraph of \(G_{i}\). Then,\[\rho_{d}(\mathcal{G},C)=\sum_{j=0}^{m}P(G_{j})I(G_{j},C,d)=\sum_{j=i}^{m}P(G_{j})= p(\epsilon_{i}).\]  
For any set \(K\subseteq V\) with \(\rho_{d}(\mathcal{G},K)>0\), the set \(K\) can form a \(d\)-core only in the possible worlds \(\{G_{i},G_{i+1},\ldots,G_{m}\}\). Thus, \(\rho_{d}(\mathcal{G},K)\leq\rho_{d}(\mathcal{G},C)\). This completes the proof.  
The following observation again uses the fact that there are only a polynomial number of possible worlds under the LRO model.  
**Observation 3**: _The Individual-Core problem is polynomial time solvable on uncertain graphs under the LRO model._  
Clearly, for each \(0\leq i\leq m\), the While-loop in Algorithm 1 computes the maximal \(d\)-core in \(G_{i}\). Therefore, for each \(v\), \(q_{d}(v)=p(e_{i})\), where \(i\) the smallest index such that the non-empty \(d\)-core contains \(v\). Since the number of possible worlds are \(m+1\), for each vertex \(v\in V\), the probability \(q_{d}(v)\) can be computed in polynomial time. Thus, for a given uncertain graph \(\mathcal{G}=(V,E,p)\), an integer \(d\) and probability threshold \(\theta\), the set \(\{v\mid q_{d}(v)\geq\theta\}\) is the optimum solution to the Individual-Core problem.