# Layered Graphs: Applications and Algorithms
## 4 Correctness and Complexity
Lemma 3: _If \(k=\Theta((\log n)^{1+\epsilon})\), for any \(\epsilon>0\) then, the MIS Algorithm, MVC Algorithm and MDS Algorithm run in quasi-polynomial time._  
Proof: The time complexities of all these algorithms can be written as \(O(f(n)g(k)2^{ck})\), where \(f(n)=\Theta(n)\), \(g(k)=O(k)\) and \(c=O(1)\). Thus, when \(k=\Theta((\log n)^{1+\epsilon})\) for \(\epsilon>0\), the complexities for all the algorithms will be quasi-polynomial. Theorem 4: _The MCD Algorithm correctly computes the cardinality of a connected minimum dominating set for \(LG_{k}\) with a time complexity of \(O(n^{1+\epsilon})\) for any \(\epsilon>0\) when \(k=O(\log n)^{\alpha}\) and \(\alpha<1\). The space complexity of the algorithm is \(O(nk)\)._  
Proof: First, we show that the algorithm correctly computes the cardinality of a connected minimum dominating set. Consider the structure of CDS on a connected graph, \(G\). Let \(V\) be arbitrarily partitioned into \(V^{1},V^{2}\), where both \(\mid V^{1}\mid>0\) and \(\mid V^{2}\mid>0\). Let \(G_{1}\) be the subgraph of \(G\) induced by \(V^{1}\), and let \(G_{2}\) be the subgraph of \(G\) induced by \(V^{2}\). Let \(M_{1}\subseteq V^{1}\) and \(M_{2}\subseteq V^{2}\) be DSs of \(G_{1}\) and \(G_{2}\). Let \(C\) be the cut \((M_{1},M_{2})\) and let \(E^{C}\) be the edges that cross this cut. Clearly, \(M=M_{1}\bigcup M_{2}\) is DS for \(G\). Further, \(M\) is a CDS for \(G\) if \(\mid E^{C}\mid>0\), and \(M\) forms a connected component in \(G\). For a given partition \(V^{1},V^{2}\) of \(V\), \(M\) is a MCD if it minimizes \(\mid M_{1}\mid+\mid M_{2}\mid\), where \(M\) forms a connected component in \(G\). Let \(G\) be a \(LG_{k}^{n,q}\); in particular, let \(G\) be a \(LG_{k}^{n,q}\). Let \(V^{1}=\bigcup_{j=1}^{q-1}V_{j}\) and \(V^{2}=V_{q}\). Let \(G_{1}\) be the subgraph of \(G\) induced by \(V^{1}\), and let \(G_{2}\) be the subgraph of \(G\) induced by \(V^{2}\). Let \(M_{1}\subseteq V^{1}\) and \(M_{2}\subseteq V^{2}\) be DSs of \(G_{1}\) and \(G_{2}\), respectively. Let \(C\) be the cut \((M_{1},M_{2})\), and let \(E^{C}\) be the edges that cross this cut. Note that \(E^{C}=E_{q-1}\)\(q\). When the algorithm processes layer \(q\), it chooses \(M=M_{1}\bigcup M_{2}\), such that \(\mid M_{1}\mid+\mid M_{2}\mid\) is minimized where \(M\) forms a connected component in \(G\). Thus, the theorem follows. Similarly, \(count_{ij}\) gives the number of ways a CDS of minimum cardinality can be formed when the vertices chosen in layer \(i\) are given by \(j\). Thus, \(\forall j\Sigma count_{ij}\) corresponding to the minimum value of \(\forall jsol_{qj}\) yields the total number of MDSs. The time complexity of the algorithm is analyzed below. We presumed that similar prerequisites as in Theorem 3 were provided. The steps are presented below. * A global structure, \(sol\), consisting of \(sol_{0}\) and \(sol_{1}\), corresponding to the previous and current layers, is maintained for the whole algorithm. The final solution for the problem can be determined just by using information from \(sol_{0}\) and \(sol_{1}\). This structure is maintained for the whole algorithm and not for every layer. * \(sol_{0}\) and \(sol_{1}\) consist of a maximum of \(B_{k}2^{k}\) triples of the form \((lo,un,r)\). This corresponds to a maximum of \(B_{k}\) component layouts \((lo)\), \(2^{k}\) masks, \(un\) undominated vertices of the current layer and a maximum of \(2^{k}\) triples, \(r\), of the form \((m,s,c)\), for every unique pair \((lo,un)\). Here, \(m\) is the mask of the current layer that produced the respective (component layout, undominated vertices) pair; \(s\) is the minimum cardinality of the sub-solution corresponding to mask \(m\) and pair \((lo,un)\); and \(c\) is the count of \(s\) corresponding to mask \(m\) and pair \((lo,un)\). * Throughout the algorithm, \(sol_{0}\) and \(sol_{1}\) are maintained by clearing \(sol_{0}\) when the current layer is processed and the information of \(sol_{1}\) is used as \(sol_{0}\) for the next layer.