# Sorting by Multi-Cut Rearrangements +
## 3 Sorting by Multi-Cut Rearrangements in Permutations
### Hardness for Constant Number of Cuts
#### 3.1.1 Breakpoints and Cycle Graph  
See Figure 4 for an illustration of the definitions in this section. For a permutation \(S\) of length \(n\), we assume that the alphabet of \(S\) is \(\{1,2,\ldots,n\}\). We further write \(S_{0}=0\) and \(S_{n+1}=n+1\) (they are considered as _implicit_ elements: they may not be part of rearrangements, but allow all other characters to have another element before and after). For a rearrangement \(r\) transforming \(S\) into \(S^{\prime}\), we write \(r(S)=S^{\prime}\) and \(r(S,T)=(S^{\prime},T)\). The _cycle graph_\(\mathcal{C}(S,T)\) of strings \(S\) and \(T\) is the graph over \(n+1\) vertices \(\{0,1,\ldots,n\}\) with arcs \(T_{j}\to S_{i}\) if \(T_{j+1}=S_{i+1}\). Every vertex has indegree and outdegree 1, so the graph is a disjoint union of cycles. Self-loops are called _trivial cycles_ (when seen as a cycle) or _adjacencies_ (when seen as an arc); other arcs are _breakpoints_. An element (or vertex) \(x\) is an adjacency (resp. breakpoint) according to its outgoing arc (we use transparently the bijection between a vertex and its outgoing arc). A _\(k\)-cycle_ is a cycle of length \(k\). The _next breakpoint_ of breakpoint \(x\to y\) in \(\mathcal{C}(S,T)\) is \(y\) (or equivalently, the outgoing arc of \(y\)). \begin{table}
\begin{tabular}{|c||c|c|c|c|} \hline \(\ell\)\(k\) & 3 & 4 & \(O(1)\) & parameter & part of the input \\ \hline \hline \(1\) & \multicolumn{3}{|c|}{\(\mathsf{P}\) (Section 1.3)} & \multicolumn{3}{|c|}{\(\mathsf{NP}\)-hard:} \\ \hline parameter & \(\mathsf{FPT}\) (Theorem 9) & \multicolumn{3}{|c|}{\(\mathsf{FPT}\) (Theorem 9)} & \multicolumn{3}{|c|}{\(\mathsf{For}\ell\geq 2\) (Theorem 8)} \\ \hline part of the input & \multicolumn{3}{|c|}{\(\mathsf{NP}\)-hard [12]} & \multicolumn{3}{|c|}{\(\mathsf{For}\,k\geq 5\) (Theorem 7)} \\ \hline \end{tabular}
\end{table} 
Table 3: Summary of the results for Sorting by Multi-Cut Rearrangements in permutations. Additionally, \(\mathsf{Opt}\)-SMCR admits a 2-approximation algorithm (Theorem 10). We write \(\mathcal{C}_{x}(S,T)\) for the cycle of \(\mathcal{C}(S,T)\) containing element \(x\). A cycle graph (and, by extension, a pair of sequences generating this cycle graph) is \(k\)-_cyclic_ if it contains only adjacencies and \(k\)-cycles. A rearrangement \(r\) applied to a permutation \(S\)_cuts_ an element \(x\), \(0\leq x\leq n\), if \(r\) cuts between \(x=S_{i}\) and \(S_{i+1}\). Furthermore, \(r\)_solves breakpoint_\(x\) if \(r\) cuts \(x\) and \(x\) is an adjacency in \(r(S)\). A rearrangement \(r\)_solves a cycle_ if it solves all breakpoints in it. We write \(d_{b}(S,T)\) for the number of breakpoints of \(\mathcal{C}(S,T)\). A \(k\)-cut rearrangement is _efficient_ if it solves \(k\) breakpoints. A pair \((S,T)\) is \(k\)-_efficiently sortable_ if there exists a sequence of efficient \(k\)-cut rearrangements transforming \(S\) into \(T\). The following is a trivial generalization of a well-known lower bound for the transposition distance. **Proposition 1**. : _A \(k\)-cut rearrangement may not solve more than \(k\) breakpoints, so \(S\) needs at least \(\frac{d_{b}(S,T)}{k}\)\(k\)-cut rearrangements to be transformed into \(T\). Furthermore, the bound is reached if, and only if, \((S,T)\) is \(k\)-efficiently sortable._  
**Proposition 2**. : _If \(r\) solves a breakpoint, it cuts the next breakpoint in the cycle graph._  
Proof. : Let \(x\to y\) be an arc of the cycle graph, and let \(x^{\prime}\) be the successor of \(x\) in \(T\) as well as the successor of \(y\) in \(S\). If \(r\) solves \(x\), then \(r\) joins a block ending in \(x\) with a block starting in \(x^{\prime}\), so \(x^{\prime}\) is the first element of some block of \(r\). Thus, \(y\) is the last element of some block of \(r\), and \(r\) cuts the breakpoint \(y\) in \(\mathcal{C}(S,T)\). Figure 4: Example of a 3-cut rearrangement scenario from \(S=52\,47\,38\,6\,19\) to \(T=1\,2\,3\,4\,5\,6\,7\,8\,9\) using cycle graphs.