# Layered Graphs: Applications and Algorithms
## 2 Layered Graph
A conflict graph, \(G\), is constructed from an optimum pairing diagram where a vertex denotes a special edge-pair, and an edge exists between a pair of vertices that are in conflict. The computation of the short reversal distance is reduced to the computation of MIS on \(G\). \(G\) consists of several subgraphs, \(\forall_{i}\ G_{i}\), each having, at most, \(k\) vertices, where each vertex corresponds to a symbol in \(\Sigma\). Each \(G_{i}\) is a subgraph of the \(K_{k}\) clique. The vertices, \(u\in G_{i},v\in G_{j}\ (i\
eq j)\), can have a conflict only if they correspond to the same symbol. Further, they share a common edge in the optimum pairing diagram. In this particular scenario, the layered graphs arise naturally. Further, such layered graphs are LLGs. In this framework, the computation of MIS on a LLG is a necessary component in the computation of the corresponding short reversal distance. Considering a tribal society \(S\) consisting of some villages on a bank of a river, a village consists of a few families where each family has its own _family-head_. The family-heads of a given village know one another, and they also interact with specific family-heads of adjacent villages for trade (of produce) and partnership (collaboration in farming etc.). If one models this society as a social network, where a family-head is denoted by a vertex and an interaction (among family-heads) is denoted by an edge, then one obtains a layered graph. In this social network, identifying the smallest set of influencers is a natural pursuit (whose solution is given by computing MDS). These applications motivate the study of MIS, MDS and other graph theoretic problems on layered graphs. In general, graph theoretic problems, like subgraph isomorphism, and its variations have extensive applications in computational biology, e.g., references [31; 32]. This article designs algorithms for \(LG_{k}\) where every vertex within a given layer gets a label from \(\{1,2,3,\ldots,k\}\). The results are applicable for any restrictions of \(LG_{k}\), like \(LLG\), \(SLG\), etc. Consider a layered graph, \(G\), whose first \(a\) layers and last \(b\) layers do not have any edges. The graph is not a \(CLG\); however, the MCV of \(G\) is the same as the MCV of the subgraph where the first \(a\) and the last \(b\) layers are removed. Further, if every layer has at least one intra-layer edge, then MCV can be computed only on \(CLG\). MCD is well defined only for \(CLG\) because it must dominate all vertices. The complete graph on \(k\) vertices, a _clique_ on \(k\) vertices, is denoted by \(K_{k}\). Consider a graph, \(G\), formed from several copies of \(K_{k}\), say \(G_{1},G_{2},\ldots,G_{q}\), where, in addition to the edges that exist in each of \(G_{i}\), an edge is introduced between every pair, \(uv\): \(u\in G_{i}\) and \(v\in G_{i+1}\). We denote this particular graph, \(G\), that has \(q\) layers with \(K_{k}^{q}\). The class of \(k\)_-restricted layered graphs_ are in fact subgraphs of \(K_{k}^{q}\). Thus, we call \(K_{k}^{q}\) a _full_\(LG_{k}^{q}\). Likewise, a \(LLG\) that is defined on \(q\) cliques, where for any \(i,i+1\), for all values of \(l\), an edge is introduced between vertex \(l\) of layer \(i\) and vertex \(l\) of layer \(i+1\), is called a _full_\(LLG_{k}^{q}\). The number of layers in \(LG_{k}\) i.e., \(q\) is bound by \(n/k\leq q\leq n\). A subgraph of \(G\)_induced_ by vertices \(u_{1},u_{2},\ldots,u_{i}\) consists of all vertices \((u_{1},u_{2},\ldots,u_{i})\) and all the edges restricted to them. We designed algorithms that compute the cardinalities of MVC, MIS and MDS of any subgraph of \(K_{k}^{q}\) i.e., \(LG_{k}^{n,q}\) in polynomial time when \(k=O(\log n)\) and the cardinalitiesof MCV and MCD in polynomial time when \(k=O((\log n)^{\alpha})\), \(\alpha<1\). Additionally, these algorithms report the corresponding numbers of MISs, MVCs, MDSs, MCVs and MCDs in \(LG_{k}^{n,q}\).