# Parameterized Optimization in Uncertain Graphs--A Survey and Some Results
## 3 Definitions Related to Graphs  
Every graph we consider in this work are simple undirected graphs unless. A graph \(G=(V,E)\) is an undirected graph with vertex set \(V\) and edge set \(E\). We denote the number of vertices and edges by \(n\) and \(m\), respectively. For a vertex \(v\in V\), \(N(v)\) denotes the set of neighbors of \(v\) and \(N[v]=N(v)\cup\{v\}\) is the closed neighborhood of \(v\). For each vertex \(v\in V\), \(deg_{G}(v)\) denote the degree of the vertex \(v\) in \(G\). When \(G\) is clear in the context \(deg(v)\) is used. The maximum degree of the graph \(G\), denoted by \(\Delta(G)\), and the minimum degree of the graph \(G\), denoted by \(\delta(G)\), are the maximum and minimum degree of its vertices. When \(G\) is clear in the context \(\Delta\) and \(\delta\) is used. Other than this, we follow the standard graph theoretic terminologies from Reference [44]. We define some special notations for the uncertain graphs as follows. Given a vertex \(v\in V\), let \(E(v)\subseteq E\) denote the set of all edges incident on \(v\). Given a subset of vertices \(C\subseteq V\), let \(E(C)=\cup_{v\in C}E(v)\) denote the edge set of the vertex-induced uncertain subgraph \(\mathcal{G}[C]\). Similarly, given an edge set \(F\subseteq E\), let \(V(F)=\cup_{e=uv\in F}\{u,v\}\) denote the vertex set of the edge-induced uncertain graph \(\mathcal{G}[F]\). We study the parameterized complexity of the coverage problems and \(k\)-core problem on uncertain graphs. We follow the standard parameterized complexity terminologies from Reference [40]. We define the parameter treewidth that will be relevant to our discussion. **Definition 4** (Tree Decomposition [45; 46]). : _A tree decomposition of a graph \(G\) is a pair \((X,H)\) such that \(H\) is a tree and \(X=\{X_{i}\subseteq V:i\in H\}\). For each node \(i\in H\), \(X_{i}\) is referred to as_ bag _of \(i\). The following three conditions hold for a tree decomposition \((X,H)\) of the graph \(G\)._  
1. _For each vertex_ \(v\in V\)_, there is a node_ \(i\in H\) _such that_ \(v\in X_{i}\)_._
2. _For each edge_ \(uv\in E\)_, there is a node_ \(i\in H\) _such that_ \(u,v\in X_{i}\)_._
3. _For each vertex_ \(v\in V\)_, the induced subtree of the nodes in_ \(H\) _that contains_ \(v\) _is connected._The _width_ of a tree decomposition is the \(\max_{i\in H}(|X_{i}|-1)\). The _treewidth_ of a graph, denoted by \(tw\), is the minimum width over all possible tree decompositions of \(G\). An example of a tree decomposition is illustrated in Figure 2. For our algorithm, we require a special kind of decomposition, called the _nice tree decomposition_ which we define below. **Definition 5** (Nice tree decomposition [46]). : _A nice tree decomposition is a tree decomposition, rooted by a node \(r\) with \(X_{r}=\emptyset\) and each node in the tree decomposition is one of the following four type of nodes._  
1. **Leaf node. **_A node \(i\in H\) with no child and \(X_{i}=\emptyset\)._
2. **Introduce node. **_A node \(i\in H\) with one child \(j\) such that \(X_{i}=X_{j}\cup\{v\}\) for some \(v\
otin X_{j}\)._
3. **Forget node. **_A node \(i\in H\) with one child \(j\) such that \(X_{i}=X_{j}\setminus\{v\}\) for some \(v\in X_{j}\)._
4. **Join node. **_A node \(i\in H\) with two children \(j\) and \(g\) such that \(X_{i}=X_{j}=X_{g}\)._  
An example of four types of nodes is illustrated in Figure 3. Given a tree decomposition \((X,H)\) of a graph \(G\) with width \(k\), a nice tree decomposition \((X^{\prime},H^{\prime})\) with same width and \(\mathcal{O}(nk)\) nodes can be computed in time \(\mathcal{O}(nk^{2})\)[46]. Hereafter, we will assume that the tree decompositions considered are nice. For each node \(i\in H\), let \(H_{i}\) denote the subtree rooted at \(i\). Let \(n_{i}=|X_{i}|\). Let \(X_{i}^{+}\) be the set of all vertices in the bag of nodes in the subtree \(H_{i}\). \[X_{i}^{+}= \begin{cases}X_{i}&\text{if $i$ is a leaf node}\\ X_{i}\cup\bigcup\limits_{j\in ch(i)}X_{j}^{+}&\text{if $i$ is a non-leaf node,}\end{cases}