# Layered Graphs: Applications and Algorithms
## 1 Introduction  
A string is a sequence of symbols from an alphabet \(\Sigma\), in which a symbol can be repeated. An _adjacent swap_ exchanges two consecutive elements in a sequence [1,2]. In a _signed string_ (\(\pi\), \(\forall\), \(\pi[i]\)) the following signs are assigned: \(+\) for normal orientation and \(-\) for reverse orientation. Adjacent swap over positions \(i\), \(i+1\) are denoted by (\(i+1\)). For unsigned strings (\(\pi\)), where \(\pi=\pi[1],\pi[2],\pi[3],\ldots,\pi[i],\pi[i+1],\ldots,\pi[n]\), \(\pi\) transforms into \(\pi^{\prime}\), where \(\pi^{\prime}=\pi[1],\pi[2],\pi[3],\ldots,\pi[i-1],\pi[i+1],\pi[i+2],\ldots,\pi[n]\). For signed strings (\(\pi\)), where \(\pi=\pi[1],\pi[2],\pi[3],\ldots,\pi[i],\pi[i+1],\ldots,\pi[n]\), \(\pi\) transforms into \(\pi^{\prime}\), where \(\pi^{\prime}=\pi[1],\pi[2],\pi[3],\ldots,\pi[i-1],-\pi[i+1],-\pi[i],\pi[i+2], \ldots,\pi[n]\). Two strings are _compatible_ under some operation if they can be transformed into each other with the operation. That is, the unsigned string (2, 1, 3, 2) is compatible with (2, 1, 2, 3), whereas it is not compatible with (3, 2, 1, 1). The computation of the minimum number of adjacent swaps required to transform one given string into another compatible string, i.e., the _adjacent swap distance_, has applications in genetics and music theory [1]. A _1-flip_ toggles the orientation of a particular \(\pi[i]\); it is denoted by \(f_{1}(i)\). It changes the sign of \(\pi[i]\). When it is applied to a signed string (\(\pi\)), where \(\pi=\pi[1],\pi[2],\pi[3],\ldots,\pi[i],\pi[i+1],\ldots,\pi[n]\), \(\pi\) transforms into \(\pi^{\prime}\), where \(\pi^{\prime}=\pi[1],\pi[2],\pi[3],\ldots,\pi[i-1],-\pi[i],\pi[i+1],\pi[i+2], \ldots,\pi[n]\). A _short reversal_ is either a (1-_flip_) or an adjacent swap. The _short reversal distance_ is the minimum number of short reversals required to transform a signed string into another compatible string. Two strings are compatible under short reversals if and only if their unsigned versions, i.e., the strings whose signs are disregarded, are compatible [1]. The computation of the short reversal distance between \(\alpha\) and \(\beta\) is reduced to the computation of the cardinality of the maximum independent set on a conflict graph constructed from \(\alpha\) and \(\beta\). It has applications in HOX gene clusters in vertebrate evolution [2; 3]. In music theory, a composition is represented as a string. The smaller the distance between two patterns (compositions), the more similar they are [4]. The maximum independent set problem on a graph, \(G=(V,E)\), seeks to identify a subset of \(V\) with maximum cardinality, such that no two vertices in the subset have an edge between them. If \(V^{*}\subseteq V\) is the maximum independent set (or MIS for short) of \(G\), then \(\forall u,v\in V^{*},\ (u,v)\
otin E\). In this article, \(G\) is undirected, so an edge \((u,v)\) is understood to be an undirected edge. [PERSON] proposed a method for proving problems to be NP-complete [5]. The maximum independent set problem on a general graph is known to be NP-complete [6]. Certain classes of graphs have a polynomial time solution for this problem. Such algorithms are known for trees and bipartite graphs [7], chordal graphs [8], cycle graphs [9], comparability graphs [10], claw-free graphs [11], interval graphs and circular arc graphs [12]. The maximum weight independent set problem is defined on a graph where the vertices are mapped to corresponding weights. The maximum weight independent set problem seeks to identify an independent set where the sum of the weights of the vertices is maximized. On trees, the maximum weighted independent set problem can be solved in linear time [13]. Thus, for several classes of graphs, MIS can be efficiently computed. [PERSON] et al. designed an \(O(n)\) time algorithm to solve the maximum weight independent set problem on an interval graph with \(n\) vertices, given its interval representation with a sorted endpoints list [14].