# Layered Graphs: Applications and Algorithms
## 3 Algorithm
### MDS and MCD  
Let an MDS of \(LG_{k}^{n,q}\) be \(V^{*}\), such that, \(V^{*}=\bigcup_{j=1}^{q}V_{j}^{*}\), where \(V_{j}^{*}\) represents the vertices in this MDS from layer \(j\). Clearly, \(V_{j}^{*}\) may not be a dominating set of layer \(j\) because the vertices of \(V_{j}\) can be dominated by any subset of \(V_{j-1}^{*}\bigcup V_{j}^{*}\bigcup V_{j+1}^{*}\). In Figure 5, \(e\in G_{2}\) is dominated by \(d\in G_{1}\). It follows that \(\bigcup_{j=1}^{p+1}V_{j}^{*}\) must dominate all vertices in \(\bigcup_{j=1}^{p}V_{j}\). Further, \(V^{*}=\bigcup_{j=1}^{q-1}V_{j}^{*}\bigcup V_{q}^{*}\) must dominate \(\bigcup_{j=1}^{q}V_{j}\). A vertex that is not dominated is _undominated_. Consider mask \(j\) in layer \(i\), where \(cs_{i,j}\bigcup cs_{i-1,l}\) dominates layer \(i-1\). This particular subset of vertices can leave some vertices in layer \(i\) undominated. The number of such choices is \(2^{k}\); each choice is denoted by a \(k\)-bit variable that we call a mask--here, a mask of _exclusion_. Further, when one processes layer \(i+1\), this information is critical. We show that the \(O(2^{k})\) triples stored for each mask of a given layer suffice to compute MDS of \(LG_{k}\). For a chosen mask, \(j\), in layer \(i\), it suffices to store \(2^{k}\) triples of the form \((u,s,c)\). Here, \(u\) is the mask of the vertices that are _undominated_ in layer \(i\), \(s\) is the cardinality of the vertices chosen so far and \(c\) is the number of choices corresponding to \(u\) for a particular \(j\) in layer \(i\). Figure 4: MCV: The vertices of a minimum connected vertex cover are \(\{b,c,d,e,g,h,i\}\) from \(G_{1}\) and \(\{b,c,d,e,f,h,i\}\) from \(G_{2}\). The cardinality of any MCV of \(G\) is 14. The vertices of MCV are shown in larger bold font. Figure 3: MVC: The vertices of a minimum vertex cover are \(\{a,b,d,f,h\}\) from \(G_{1}\) and \(\{a,c,d,e,h,i\}\) from \(G_{2}\). The cardinality of any MVC of \(G\) is 11. The vertices of MVC are shown in larger bold font. MCD has an additional requirement compared to MDS, i.e., \(V^{*}\) must form a single component (please see Figure 6). For possible combinations of component layouts of the current and previous layer masks, see MCV. For MCD, it suffices to store \(O(B_{k}2^{k})\) triples of the form \((lo,un,r)\), where \(B_{k}\) is the \(k\)-th Bell number. This corresponds to \(O(B_{k})\) component layouts, \(lo\), for a mask, \(j\), and \(O(2^{k})\) masks \(un\) of the vertices that are \(not\) dominated in layer \(i\) and \(O(2^{k})\) triples \(r\) of the form \((m,s,c)\) for every unique pair of \((lo,un)\). Here, \(m\) is the mask of the current layer that produces the respective \((lo,un)\) pair, i.e., mask \(j\), while \(s\) and \(c\) are same as that for MDS, corresponding to mask \(m\) and pair \((lo,un)\). The particular mask in the previous layer that is the cause of a particular triple in the current layer needs not be carried forward. So, for MDS, \(sol_{i,j}\) indicates an array of \(2^{k}\) triples. As for MCD, it indicates \(O(B_{k}2^{k})\) triples where \(O(2^{k})\) triples are associated with each of the \(O(B_{k}2^{k})\) unique pairs of \((lo,un)\). Also, when \(k=O(\log n)\) for MDS and \(k=O(\log n)^{\alpha}\) where \(\alpha<1\) for MCD, the algorithm runs in polynomial time. Consider the following analysis for MDS. Let mask \(j\) be chosen in layer \(i\); it can potentially be combined with every mask (\(O(2^{k})\) masks) of the previous layer. Thus, potentially, (\(O(2^{k})\)) triples need be stored. Further, the total number of triples of the form \((un,s,c)\) is \(\Omega(n.2^{k})\), because \(un\) can potentially assume any \(0,\ldots,2^{k}-1\); \(s\) is \(O(n)\) and \(c\) can, in fact, be exponential in \(\frac{n}{k}\). Here, we make the following critical observations:  
* Let the chosen mask for layer \(i\) be \(j\). When all the compatible vertex sets of the previous layer are considered, then let the resultant triples for the choice of \(j\) in layer \(i\) be set as \(S\).