# Layered Graphs: Applications and Algorithms
## 4 Correctness and Complexity
* \(sol_{0}\) is initialized with the triple \((lo,un,r)\), corresponding to \(2^{k}\) masks of the first layer. The initialization takes \(O(k^{2}2^{k})\). * A candidate sub-solution for layers \(1,\ldots,i\) induces connected components in layer \(i\) that are defined in terms of vertices of layer \(i\). We call this the component layout. * The number of component layouts is upper bounded by \(B_{k}\), the number of ways of partitioning \(k\) vertices of a layer. Here, \(k=f(n)\), \(f(n)=O(\log n)^{\alpha}\), \(\alpha<1\). \(B_{k}=O(f(n)!)\). From Lemma 1, we know that \(f(n)!=O(n^{\epsilon})\), for any \(\epsilon>0\). * A mask \(j\) of the current layer can be combined with a component layout for mask \(l\) of the previous layer to form a new component layout for the current layer. With the same mask, \(l\), \(j\) can form a new mask corresponding to the undominated vertices of the current layer. * Every such unique pair of \((lo\), \(un)\), where \(lo\) is component layout and \(un\) is mask of undominated vertices, is maintained, and a list of triples \(r\), consisting of triples of the form \((m,s,c)\), is associated with it. Here, \(m\) is the current layer mask, \(s\) is the minimum cardinality of the sub-solution corresponding to \(m\), and \(c\) is the count of \(s\). The number of such tuples, \((lo,un,r)\), is upper bounded by \(B_{k}2^{2k}\), where \(B_{k}2^{k}\) is the possible number of unique pairs of \((lo,un)\), and \(2^{k}\) is the possible number of triples that can exist for each pair. * Starting from the \(i\)-th layer, \(i>1\), every \(2^{k}\) masks of the current layer and the triple values from the previous layer are used to generate the triples for the current layer. * For a unique pair \((lo,un)\) in the previous layer, if mask \(j\) dominates the undominated vertices of mask \(un\), and forms a connected component with the layout, \(lo\), then we consider that a sub-solution using mask \(j\) is feasible. Here, a mask, \(j\), and a component layout, \(lo\), are considered to form a connected component if every component in \(lo\) has at least one edge with a node in mask \(j\). Each such check takes \(O(k^{2})\) time. So, the total time to determine if a sub-solution with mask \(j\) is feasible is \(O(k^{2})\). * If a mask, \(j\), can feasibly give a sub-solution, then it is combined with the component layout, \(lo\), of the previous layer to form a new component layout for the current layer corresponding to mask \(j\). This is performed using a DFS which takes \(O(k^{2})\) for the given input matrix. * Mask \(j\) is then combined with mask \(l\) of the previous layer, corresponding to the pair \((lo,un)\) that is under consideration, to form a mask for the current layer vertices that are not dominated by \(j\) or \(l\). This takes \(O(k^{2})\) time. * Using the mask, \(j\), of the current layer and minimum cardinality, \(s\), for the pair \((lo,un)\) of the previous layer, the new cardinality for the sub-solution is computed. * The count of the new cardinality will be same as that of \(c\) of the \((lo,un)\) pair for the previous layer. * This new pair of the component layout and undominated mask computed for mask \(j\) of the current layer are checked with the existing pairs of the current layer to determine if it is unique or not. We maintain the structure of the triples such that an entry can be accessed in \(O(1)\) time, indexed by the pair \((lo,un)\) and the corresponding mask \(m\) for the previous and the current layer. * If it is unique, the triple value, consisting of the newly computed \((lo,un)\) pair and its corresponding triple, consisting of the mask \(j\), respective cardinality and the count, are added as a new triple for the current layer. * Consider that the current mask \(j\) produces the new pair \((lo,un)\) with values \(s=s_{x}\) and \(c=c_{x}\). If the new pair is not unique, then there are three cases. Consider the existing entry of the \((lo,un)\) pair and the corresponding \(j\) to have values \(s=s_{y}\) and \(c=c_{y}\). 1.