# Layered Graphs: Applications and Algorithms
## Appendix A
### MIS Algorithm  
```
Input: \(LG_{k}^{n,q}\) Output: The cardinality of MIS and the count of the maximum independent sets. Initialization: \(\forall i\ sol_{0i}=sol_{1i}=0\); \(\forall i\ count_{0i}=count_{1i}=0\); //\(sol_{ij}:\) The maximum value of an independent set up to layer \(i\) where the chosen //vertices of the layer \(i\) are given by the binary value of \(j\). //\(count_{ij}:\) the number of ways the \(j\)th mask in layer \(i\) yields the corresponding maximum value. //\(valid(i,j)\) is a Boolean function that returns true if the vertex assignment corresponding to //the binary value of \(j\) in layer \(i\) forms an IS. Otherwise it returns false. //\(\wedge\) is the bitwise AND operator. //\(cardinality(j)\) is the number of bits that are set in the binary representation of \(j\). // For each \(sol_{ij}\), one \(k\)-bit variable that remembers the mask of the layer \(i-1\) that // yielded \(sol_{ij}\) will help in constructing MISs. The union of such masks (1/layer) is an MIS. for(\(i=0,...,2^{k}-1\))do if\(valid(1,i)\)then// for layer \(1\)\(count_{0i}=1;sol_{0i}=cardinality(i)\); // No. of valid ISs of layer \(1\) endif endfor for(\(p=2,....q\))do//For layers 2 through maximum for(\(j=0,....2^{k}-1\))do//For all masks of current layer if\(valid(p,j)\)then//j is valid \(size\gets 0\) for(\(l=0,...,2^{k}-1\))do//Masks of previous layer if(\((count_{ql}>0)\wedge(compatible(j,l)))\)then//\(sol_{0l}=0\rightarrow\)Invalid IS if(\(cardinality(j)+sol_{0l}\geq size\))then//Better IS for the current mask if(\(cardinality(j)+sol_{0l}>size\))then size\(=cardinality(j)+sol_{0l};count_{0l}=count_{0l}+1\) endif endfor\(count_{0l}\gets count_{0l}+1\) endif endfor//Masks of previous layer endfor//Masks of previous layer for(\(l=0,...,2^{k}-1\))do//Masks of previous layer if(\(size=cardinality(j)+sol_{0l}\))then//Instance of max \(count_{1j}\gets count_{1j}+count_{0l}\); // Count corr. to max wrt mask=\(j\) endif endfor//Masks of previous layer \(sol_{1j}\gets size\) endif//j is valid endfor//For all masks of current layer \(\forall x\ count_{0x}\gets count_{1x};sol_{0x}\gets sol_{1x};count_{1x} \gets sol_{1x}\gets 0\); endfor//For layers 2 through maximum \(best\gets 0;sum\gets 0\); for(\(i=0,...,2^{k}-1\))do if\(sol_{0l}>best\)then//Get the max value of \(\forall isol_{pi}\) \(best=sol_{0i}\); endif endfor for(\(i=0,...,2^{k}-1\))do if\(sol_{0l}=best\)then//Corr. to the best value of



### MVC Algorithm
```
Input:\(LG_{k}^{n,q}\) Output: The cardinality and the count for the resp. problem. //\(sol_{ij}\) : The minimum value of a vertex cover up to layer \(i\) where the chosen //vertices of the layer \(i\) are given by the binary value of \(j\). //\(valid(i,j)\) is a Boolean function that returns true if the vertex assignment corresponding to //the binary value of \(j\) in layer \(i\) forms a VC. Otherwise it returns false. //\(count_{ij}\) : the number of ways the \(j\)th mask in layer \(i\) yields the corresponding minimum value. //\(cardinality(j)\) is the number of bits that are set in the binary representation of \(j\). for\((i=0,...,2^{k}-1)\)do if\(valid(1,i)\)then //for layer 1 \(count_{0i}=1;sol_{0i}=-1\); // No. of valid VCs of layer 1 endif endfor for(\(p=2,....q\))do //For layers 2 through maximum for\((j=0,....2^{k}-1)\)do //For all masks of current layer if\(valid(p,j)\)then //\(j\) is valid \(size\leftarrow(i+1)*k\) for\((l=0,...,2^{k}-1)\)do //Masks of previous layer if\(((count_{0l}>0)\land(compatible(j,l)))\)then //\(sol_{0l}=0\rightarrow\)Invalid VC if\((cardinality(j)+sol_{0l}\leq size)\)then // Better VC for the current mask \(size=cardinality(j)+sol_{0l}\); if\((cardinality(j)+sol_{0l}=size)\)then \(count_{1j}\gets count_{1j}+count_{0l}\); else\(count_{1j}\gets count_{0l};sol_{1j}\gets size)\) endif endif endif \(sol_{1j}\gets size\) endfor//Masks of previous layer for(\(l=0,...,2^{k}-1\))do //Masks of previous layer if(\(size=cardinality(j)+sol_{0l}\);)then //Instance of max \(count_{1j}\gets count_{1j}+count_{0l}\); // Count corr.