# Layered Graphs: Applications and Algorithms
## 3 Algorithm
### MVC and MCV  
Consider a vertex cover \(V^{*}=\bigcup_{j=1}^{d}V_{j}^{*}\) of \(LG_{k}^{n_{d}l}\) where \(V_{j}^{*}\) denotes the set of vertices in \(V^{*}\) from layer \(j\). Clearly, \(V_{j}^{*}\) is a VC for layer \(j\) (please see Figure 3). \(V_{j}^{*}\) depends only on \(V_{j-1}^{*}\) and \(V_{j+1}^{*}\). Consider two adjacent layers, \(p\) and \(p+1\). \(V_{p}^{*}\bigcup V_{p+1}^{*}\) must cover all inter-layer edges between layers \(p\) and \(p+1\). Specifically, \(V^{*}=\bigcup_{j=1}^{p+1}V_{j}^{*}\) must cover all edges in the corresponding induced subgraph, including \(E_{p\ p+1}\). Similar constraints hold for MCV. Additionally, for MCV, the induced subgraph of \(V^{*}\) must be a connected component (please see Figure 4). In the sequel, the time and space complexity analyses for these problems are presented.  
Clearly, each layer must choose a mask that is a VC. In the case of MCV, when considering a mask, \(j\), for the current layer, \(i\), the following cases exist:  
1. The previous layer mask, \(l\), corresponds to one component.
2. \(l\) has more than one component, i.e., the set of vertices denoting \(l\) is partitioned into several connected components. **Case (a)**: For layer \(i\), mask \(j\) is infeasible if either (I) vertices corresponding to \(j\) and \(l\) have no edges among them or (II) all edges in \(l_{i}\) are not covered. Otherwise, \(j\) is feasible. If at least one edge exists across \(j\) and \(l\):  
1. If \(j\) is a single connected component, then the result is also a single component (consisting of all chosen vertices).
2. If \(j\) has more than one connected component and all of them connect to \(l\), then the result is also a single component.
3. If \(j\) has more than one connected component and only some of them connect to \(l\), then the result consists of many components. All components from \(j\) connected to \(l\) become one component and the rest are separate components. **Case (b)**: Every component from the previous layer corresponding to mask \(l\) must connect to some component in the current layer. Otherwise, the pair \(j\) and \(l\) is infeasible for layer \(i\). For feasible pairs the following possibilities exist:  
1. Every component in \(l\) has an edge with exactly one component in \(j\). Here, the partition is determined by \(j\).
2. A component, \(C\), in \(l\) has edges with \(C_{1},\ldots,C_{a}\) in \(j\). Then, \(C_{1},\ldots,C_{a}\) can be merged into one component as they are connected through \(C\). A particular partitioning of the current layer can occur due to various choices of \(l\). For each partition corresponding to \(j\), the sub-solution is stored with minimum cardinality. Thus, for each mask, \(j\), there are, at most, \(B_{k}\) (\(k\)-th Bell number) solutions stored. When mask \(x\) is chosen for the last layer, then the vertices of the mask must be connected to the components of the previous layer and yield a single component.  
Figure 2: MIS: Graph \(G\) consists of two layers, \(G_{1}\) and \(G_{2}\). The same graph is employed for the illustration of other problems. The vertices of a maximum independent set are \(\{b,e,f,h\}\) from \(G_{1}\) and \(\{a,d,h\}\) from \(G_{2}\). The cardinality of any MIS of \(G\) is 7. The vertices of MIS are shown in larger bold font.  
* \(feasible(j)\): Mask \(j\) must denote a VC for \(G_{i}\).
* \(compatible(j,1)\): The union of two VCs must be a VC for edges in \(G_{i-1}\), \(G_{i}\) and \(I_{i-1}\). \(i\) is the current layer. For MCV, all components of \(l\) must have edges with vertices in \(j\). If \(i=q\), then \(V^{*}\) must be one component.
* Extension: If \((cardinality(j)+sol_{i-1,l}<sol_{i,j})\)\(sol_{i,j}\gets cardinality(j)+sol_{i-1,l}\).
* Summarize: Let \(opt\gets min(\forall jsol_{q,j})\); \(count\gets 0\); \(\forall_{j}\)\(if(sol_{q,j}=opt)count\gets count+count_{q,j}\); Return \((opt,count)\)