# Layered Graphs: Applications and Algorithms
## Appendix A
### MCD Algorithm  
```
// A brief outline of the MCD Algorithm // The algorithm maintains a global structure, \(sol\), which consists of \(sol_{0}\) and \(sol_{1}\), corresponding to the previous and current layers. \(sol_{1}\) consists of \(B_{k}2^{k}\) triples of the form \((lo,un,r)\). This corresponds to a maximum of \(B_{k}\) (\(k\)-th Bell number) component layouts, \(2^{k}\) masks of undominated vertices of the current layer and a maximum \(2^{k}\) triples, \(r\), of the form \((m,s,c)\) for every unique pair \((lo,un)\). \(lo\) is a component layout, \(un\) is the mask of undominated vertices of the current layer; \(r\) is triples of the form \((m,s,c)\) where \(m\) is the mask of the current layer that produces the respective (component layout, undominated vertices) pair; \(s\) is the minimum cardinality of the sub-solution corresponding to mask \(m\) and pair \((lo,un)\); \(c\) is the count of \(s\) corresponding to mask \(m\) and pair \((lo,un)\). All unique pairs of (component layout, undominated vertices) need not yield a (sub)solution. \(sol_{0}\) consists of the same information as for the previous layer. // Mask \(j\) refers to the mask of the vertices of current layer that can yield a sub-solution (with minimum value of \(s\) for some pair \((lo,un)\)). The component layout refers to the list of the connected components of the current layer vertices (which can form a component employing some vertices from the previous layers). It is determined by the respective mask and the corr. sub-solution from the previous layer whose combination yields the minimum value of \(s\) for some pair \((lo,un)\). // If the current layer mask, \(j\), produces \((lo,un)\) pair with values \(s=s_{x}\) and \(c=c_{x}\), then we have two cases: (i) There is no entry corr. \((lo,un)\) and \(j\). Here, we just add \((lo,un)\) and \(j\) with corr. \(s\) and \(c\). (ii) There is an entry corr. \((lo,un)\) and \(j\) with \(s=s_{y}\) and \(c=c_{y}\) then, (a) if \(s_{y}=s_{x}\) then \(c_{y}\gets c_{y}+c_{x}\); (b) if \(s_{y}>s_{x}\) then \(s_{y}\gets s_{x};c_{y}<c_{x}\); (c) if \(s_{y}<s_{x}\) then no update is required. for(\(i=0,...,2^{k}-1\))do // for layer 1  Initialize \(sol_{0i}\leftarrow(lo,un,r)\); \(r\leftarrow(m,cardinality(i),1)\) endfor for(\(p=2\),..., \(q\))do // for layers 2 through \(q\) for(\(j=0\),..., \(2^{k}-1\))do // \(j\): current layer mask for(\(v=0\),..., no. of \((lo,un)\) pairs) do // Of \(sol_{0}\)  If \(j\) dominates the nodes of \(un\) of \(sol_{0}\) then continue. If every component of \(lo\) of \(sol_{0v}\) has an edge to any node in \(j\) then continue. Compute the new component layout using mask \(j\) and layout \(lo\). for(\(x=0\),..., size of \(r\) corr. \((l,u)\))do // No. of triples in \(r\)  Compute the new mask of the undominated vertices using masks \(j\)  of current layer and \(m\) corresponding to \(x\)-th triple of \(sol_{0v}\). Compute the minimum cardinality of the sub-solution corresponding to mask \(j\) for the current layer using \(s\) of the \(x\)-th triple of \(sol_{0v}\). The count of the newly computed sub-solution will be equal to \(c\)  of the \(x\)-th triple corresponding to mask \(m\). If component layout \(lo\) and the undominated mask \(un\) that are computed corr. \(j\)  do not exist in \(sol_{1}\), then insert the tuple \((lo,un,r)\), into \(sol_{1}\)  where \(r\) has a single triple whose mask is \(j\). If the \((lo,un)\) pair was already generated by \(j\) and a previous mask of the previous layer, then if needed, update the minimum cardinality and the corresponding count. Otherwise, insert the new triple \((m,s,c)\) for the corresponding \((l,u)\) pair in \(sol_{1}\). endfor endfor endfor \(best\leftarrow\inf\), \(sum\gets 0\)  Consider the values of \(sol_{1}\) in layer \(q\). Here, the component layout can be ignored as an entry would mean that it forms a connected component. For a solution to be considered, the undominated mask must be 0. for(\(i=0\),..., no. of \((lo,un)\) pairs) do // for \(sol_{1}\)  Identify \(best\), the cardinality of the optimal solution.