# Layered Graphs: Applications and Algorithms
## 4 Correctness and Complexity  
The Algorithm Generic Optimum when adapted to a specific problem, say MVC, is referred to as Algorithm MVC. The correctness is shown for MIS, MVC and MCD problems. The time complexities for MIS, MVC, and MDS are respectively \(O(nk2^{2k})\), \(O(nk2^{2k})\) and \(O(n2^{3k})\), where \(k=O(\log n)\). When \(k=\log n\) these time complexities yield \(O(n^{3}k)\), \(O(n^{3}k)\) and \(O(n^{4})\) respectively. The space complexities are \(O(nk)\), \(O(nk)\) and \(O(k2^{2k})\) respectively. When \(k=\log n\) these space complexities yield \(O(nk)\), \(O(nk)\) and \(O(kn^{2})\) respectively. For MCV and MCD problems, the time complexity is \(O(n^{1+\epsilon})\) for any \(\epsilon>0\), where the number of vertices in a layer is \(k=O((\log n)^{\alpha})\) for \(\alpha<1\). The space complexity is \(O(nk)\) for MCD and MCV. The time and space complexities of MVC and MCD are analyzed. The proofs of correctness for the remaining problems are similar. The time complexity for MDS was presented earlier. **Theorem 1**: _The MIS Algorithm correctly computes the MIS on \(LG_{k}^{n,q}\)._  
Let \(G=(V,E)\) be a graph and let \(V\) be partitioned into \(V^{1},V^{2}\). Further, let \(I_{1},I_{2}\) be the ISs of the graphs induced by \(V^{1},V^{2}\), respectively, and let \(I=I_{1}\bigcup I_{2}\). If we consider the cut, \(C=(I_{1},I_{2})\), on \(I\), where \(E^{C}\) is the set of edges crossing the cut, then it follows that \(I\) is an IS of \(G\) if \(E^{C}=\phi\). Further, the cardinality of an MIS of \(G\) is \(max(\bigvee_{E^{C}=\phi}\mid I_{1}\mid+\mid I_{2}\mid)\). It is possible that either \(\mid I_{1}\mid=0\) or \(\mid I_{2}\mid=0\). Let \(G\) be \(LG_{k}^{n,q}\). Let \(G_{1}\) be the subgraph of \(LG_{k}^{n,q}\) induced by \(V^{1}=\bigcup_{j=1}^{i}V_{j}\), and let \(G_{2}\) be the subgraph of \(LG_{k}^{n,q}\), induced by \(V^{2}=\bigcup_{j=i+1}^{q}V_{j}\). Consider the IS of \(G\). Let \(I_{1}\) and \(I_{2}\) be the independent sets of \(G_{1}\) and \(G_{2}\), respectively. Let the set of edges crossing the cut, \(C=(I_{1},I_{2})\), be \(E^{C}\). It follows that \(I=I_{1}\bigcup I_{2}\) is an IS of \(G\) with cardinality \(\mid I_{1}\mid+\mid I_{2}\mid\) when there is no edge crossing \(C\). Only the edges in \(E_{i}\,i+1\) need to be considered. Thus, the cardinality of an MIS of \(LG_{k}^{n,q}\) is equal to \(max(\bigvee_{E^{C}=\phi}\mid I_{1}\mid+\mid I_{2}\mid)\). When the last layer is processed, the cardinalities of the ISs of subgraphs induced by both \(V\) and \(V-V_{q}\) are known. Further, these ISs have maximum cardinalities with respect to the vertices chosen in layers \(q-1\) and \(q\), respectively. The theorem follows. Likewise, \(count_{ij}\) gives the number of ways that an independent set of maximum cardinality can be formed when the vertices chosen in layer \(i\) are given by \(j\). Thus, the \(count_{ij}\) corresponding to the maximum value of \(sol_{ij}\) yields the total number of MISs. **Theorem 2**. : _The MVC Algorithm correctly computes the MVC on \(LG_{k}^{n,q}\)._  
Proof. : Consider the structure of MVC on \(LG_{k}^{n,q}\). Let \(G_{1}\) be the subgraph of \(LG_{k}^{n,q}\) induced by \(V^{1}=\bigcup_{j=1}^{i}V_{j}\), and let \(G_{2}\) be the subgraph of \(LG_{k}^{n,q}\) induced by \(V^{2}=\bigcup_{j=i+1}^{i}V_{j}\). Consider a VC of \(G\). Let \(M_{1}\) and \(M_{2}\) be the vertex covers of \(G_{1}\) and \(G_{2}\), respectively. Let the set of edges crossing the cut, \(C=(M_{1},M_{2})\), be \(E^{C}\). It follows that the cardinality of a VC of \(G\) is \(\mid M_{1}\mid+\mid M_{2}\mid\) when every edge crossing \(C\) is covered by either \(M_{1}\) or \(M_{2}\). Note that the only edges from \(E_{i\,i+1}=E^{C}\) can go across the cut. Thus, the cardinality of the MVC of \(LG_{k}^{n,q}\) is equal to \(min(\mid M_{1}\mid+\mid M_{2}\mid)\) for any such cut. When the last layer is processed, this property is ensured. The theorem follows.