# Layered Graphs: Applications and Algorithms
## 4 Correctness and Complexity
If \(s_{y}=s_{x}\), then \(c_{y}\gets c_{y}+c_{x}\); 2. If \(s_{y}>s_{x}\), then \(s_{y}\gets s_{x};c_{y}\gets c_{x}\); 3. If \(s_{y}<s_{x}\), then no update is required. * The above procedure is performed until the last layer, where the final solution is computed from the current layer information corresponding to the last layer. Of all the \(B_{k}2^{k}\) pairs for the current layer, a solution is considered to be feasible if the mask for the undominated vertices for any of the \(B_{k}\) component layouts is 0, as this would mean all the vertices are dominated. The cardinality of MCD is the minimum value among all the feasible solutions. The count is then computed by considering each feasible entry with the minimum cardinality computed above and adding its corresponding count. * Thus, the solution and the corresponding count of optimal solutions for MCD problem are computed. For the whole algorithm, we maintained a global structure, as mentioned above. It consisted of a maximum of \(O(B_{k}2^{k})\) entries corresponding to unique pairs of \((lo,un)\) and another \(2^{k}\) triples for each such pair. We maintainewa this information for only the previous and the current layers. So, the space used by the data structure is \(O(B_{k}2^{2k})\). This can be shown to be equal to \(O(n^{\varepsilon})\), for any \(\epsilon>0\), based on the proof for Lemma 1. This space requirement is in addition to the space required by the input graph which is \(O(nk)\). For \(k=O((\log n)^{\alpha})\), \(O(nk)\) is the dominating term compared to \(O(n^{\varepsilon})\). So, the space complexity is \(O(nk)\). The following is the proof for time complexity of the algorithm. First, an expression for the runtime of the algorithm is derived. The initialization using the first layer takes \(O(k^{2}2^{k})\) time. For each layer after the first, the \(2^{k}\) masks of the current layer are combined with the \(B_{k}2^{k}\) pairs of the previous layer. For each pair, a current layer mask is combined with a maximum of \(2^{k}\) masks of the previous layer that generated this pair. Checking the feasibility of a mask of the current layer takes \(O(k^{2})\). Computing the new component layout and the new undominated mask takes \(O(k^{2})\) each. The undominated mask is calculated for \(2^{k}\) masks of the previous layer for each mask of the current layer. Accessing and updating an entry takes \(O(1)\) time, as mentioned above. This is done for \(O(n/k)\) layers. So, the time complexity expression can be written as  
\[ \begin{split} T&=O(\frac{n}{k}2^{k}B_{k}2^{k}(k^{2} +2^{k}k^{2}))\\ &=O(\frac{n}{k}k2^{2k}(2^{k}k^{2}))\quad\because(B_{k}=O(k!))\\ &=O(nk2^{3k}k!).\end{split}  \tag{1}\]  
If \(k=O(1)\), the time complexity becomes \(T=O(n)\). If we assume the worst case number of nodes in each layer, i.e., \(k=f(n)\), then the corresponding time complexity is \(T=O(n^{1+\varepsilon})\). as shown below. Let \(f(n)=(\log n)^{\alpha}\quad\alpha<1\)  
Let \(h(n)=n^{\gamma}\quad\gamma>0\)  
From Lemma 1 we have  
\[x!=O(n^{\gamma})\text{ for some }\gamma>0\text{, where }x=(\log n)^{\alpha}\] \[\Rightarrow f(n)!=O(n^{\gamma})=O(h(n))\]  
The running time of the algorithm is given by  
\[ \begin{split}& T=O(nk2^{3k}f(n)!)\\ &\leq cn*k*2^{3k}*h(n)\\ &\leq cn^{1+\gamma}*(\log n)^{\alpha}*2^{3(\log n)^{\alpha}}\quad (\because h(n)=n^{\gamma})\end{split} \]  
Consider \(F(n)=(\log n)^{\alpha}*2^{3(\log n)^{\alpha}}\)  
Let \(g_{1}(n)=n^{\delta}\) and \(g_{2}(n)=n^{\mu}\qquad\delta>0,\mu>0\)We know that the logarithmic functions grow slower than the polynomial functions. \[\Rightarrow(\log n)^{\alpha}\leq cg_{1}(n)\] \[\Rightarrow(\log n)^{\alpha}=O(n^{\delta})\]  
Now, we claim that \(2^{3(logn)^{\alpha}}\leq cg_{2}(n)\) for some \(\alpha<1\), a positive real number \(c\) and \(n>n_{0}\), where \(n_{0}\) is some positive intege.