# Layered Graphs: Applications and Algorithms
## 4 Correctness and Complexity
Similarly, \(count_{ij}\) gives the number of ways that a vertex cover of minimum cardinality can be formed when the vertices chosen in the layer \(i\) are given by \(j\). Thus, \(count_{qj}\) corresponding to the minimum value of \(sol_{qj}\) yields the total number of MVCs. **Theorem 3**. : _The MVC Algorithm on \(LG_{k}^{n,q}\) runs in polynomial time in \(n\) when \(k=O(\log n)\). The space required is \(O(nk)\)._  
Proof. : We presume that \(I_{i}\), the 0-1 adjacency matrix for the subgraph induced by \(V_{i}\bigcup V_{i+1}\) where the edges are restricted to \(E_{i\,i+1}\) is given. Likewise, we assume that the 0-1 adjacency matrix, \(M_{i}\), for each of \(G_{i}\) is given. Recall that \(LG_{k}^{n,q}\) was formed from \(G_{1},G_{2},\ldots,G_{q}\). For a linear graph, \(I_{i}\) is just a \(k-\)dimensional vector where, if bit \(j\) is set, then there is an edge between \(V_{ij}\) and \(V_{i+1\,j}\). * The initialization step requires \(O(2^{k})\) time. * Given a mask for layer \(i\), it can be determined whether VC is valid in \(O(k^{2})\) time with \(M_{i}\). That is, for any two \(M_{i}[a][b]\) that are set, the mask should have either a bit \(a\) or a bit \(b\) set. * Given \(I_{i}\) and two masks, \(mask1\) and \(mask2\), for layers \(i\) and \(i+1\), respectively, it can be directly determined whether the union of the two masks is a VC of the subgraph induced by \(\bigcup_{i}^{i+1}V_{j}\), of \(LG_{k}^{n,q}\), in \(O(k^{2})\) time. * In order to determine the MVC up to layer \(i\), whose mask is \(j\), \(j\) must be checked for compatibility with all masks of the previous layer. Thus, \(O(k^{2}2^{k})\) time is required. For all masks of the current layer, \(O(k^{2}2^{2k})\), time is required. For all layers, the time required is maximized when each layer has \(k\) vertices yielding \(O(\frac{n}{k}k^{2}2^{2k})=O(nk2^{2k})\) time. The time complexity is clearly exponential in \(k\); however, if \(k=O(1)\), the time complexity is \(O(n)\). The time complexity remains polynomial when \(k=O(\log n)\); specifically, \(O(n^{3}\log n)\) when \(k=\log n\). The additional space required is \(O(k2^{k})\) because for two layers, \(4.2^{k}\) masks and count variables are stored, each of size \(k\). The space required is \(O(nk)\) to store the graph and an additional space of \(O(k2^{k})\) that is needed by the algorithm. When \(k=O(\log n)\), the space complexity is \(O(nk)\). **Lemma 1**. : _Let \(0\leq\alpha<1.0\), where \(\alpha\in R^{+}\). If \(x=(\log n)^{\alpha}\), then \(x!=O(n^{\epsilon})\) for any \(\epsilon>0\)._  
Proof. : Let \(f(n)=(\log n)^{\alpha}\), \(\alpha<1\). Let \(h(n)=n^{\epsilon},\epsilon>0\). Thus, \(f(n)!=(\log n)^{\alpha}!\). Taking log on both sides we obtain:  
\[\log(\lceil f(n)!\rceil) =\log 1+\log 2+\cdots+\log(\lceil(\log n)^{\alpha}\rceil)\] \[=\sum_{x=1}^{\lceil(\log n)^{\alpha}\rceil}\log x\] \[\approx\int_{1}^{(\log n)^{\alpha}}\log xdx\] \[=[x\log x-x]_{1}^{(\log n)^{\alpha}}\] \[=\alpha(\log n)^{\alpha}\log\log n-(\log n)^{\alpha}+1\]Disregarding smaller order terms we obtain the expression: \((\log n)^{\alpha}(\alpha\log\log n)\)  
\(\alpha\log\log n=\log((\log n)^{\alpha})\). Note that \(\log n=O(n^{\mu})\) for any \(\mu>0\). Thus, \((\log n)^{\alpha}(\alpha\log\log n)<((\log n)^{\alpha}))^{(1+\mu)}\) for any \(\mu>0\). Given that \(\alpha<1\) one can always choose \(\mu\) such that \(\alpha+\alpha\mu<1\). Thus, the expression is \(O(\log n)=O(n^{\epsilon})\) for any \(\epsilon>0\). Thus, \((\log n)^{\alpha}!=O(n^{\epsilon})\). Lemma 2: \((\log n)!\) _is quasi-polynomial and \((\log n)!=n^{O(\log\log n)}\)._  
Proof: From [PERSON]'s Approximation, we have \(\log((\log n)! )\approx\theta(\log n\log\log n)\)  
\(\Rightarrow(\log n)!\approx\epsilon^{\theta(\log n\log\log n)}\)  
Thus, for some constants \(\mu\) and \(\delta\), \((n^{\delta\log\log n})\leq((\log n)! )\leq(n^{\mu\log\log n})\)  
Thus, \((f(n)! )\) is quasi-polynomial.