# Sorting by Multi-Cut Rearrangements +
## 3 Sorting by Multi-Cut Rearrangements in Permutations
### Hardness for Constant Number of Cuts
#### 3.1.3. Extending All Cycles  
We use the natural order over integers as an arbitrary total order over the nodes. The _representative_ of a cycle is its minimum node. We assume \((S,T)\) to be \(k\)-cyclic for some \(k\). A _sample_ for \((S,T)\), where \((S,T)\) is \(k\)-cyclic is a list \(X\) containing the representative from each \(k\)-cycle, and an arbitrary number of adjacencies. The \(p\)-extensions of \((S,T)\) for sample \(X=(x_{1},\ldots,x_{\ell})\) and of a rearrangement \(r\) of \((S,T)\) are, respectively, \(\Phi^{p}_{X}(S,T)=\phi^{p}_{x_{\ell}}(\ldots\phi^{p}_{x_{2}}(\phi^{p}_{x_{1}}(S,T))\ldots)\) and \(\Psi^{p}_{X}(r)=\psi^{p}_{x_{\ell}}(\ldots\psi^{p}_{x_{2}}(\psi^{p}_{x_{1}}(r))\ldots)\). For \(x_{i}\) in the sample, we write \(n_{x_{i}}=|S|+p\cdot(i-1)\), i.e., \(n_{x_{i}}\) is the size of the strings on which \(\phi^{p}_{x_{i}}\) is applied. Note that the above definition requires each \(x_{i}\) to be safe in \(\phi^{p}_{x_{i-1}}(\ldots\phi^{p}_{x_{1}}(S,T)\ldots)\). This is indeed the case by Lemma 2: either \(p=2\), there are no \(2\)-cycles, and all breakpoints are without ties, or \(p=3\), all \(2\)-cycles are tied to a single cycle \(\mathcal{C}_{x_{j}}(S,T)\) with \(j<i\), which are all different from \(\mathcal{C}_{x_{i}}(S,T)\) (since \(X\) is a sample and contains at most one element per cycle). If \((S,T)\) is \(k\)-cyclic, then \(\Phi^{2}_{X}(S,T)\) is \((k+2)\)-cyclic. Proof. : This follows from Lemma 2, since the \(2\)-extension adds \(2\) elements to each \(k\)-cycle, so \(\Phi^{2}_{X}(S,T)\) is \((k+2)\)-cyclic. If \(r\) is an efficient \(k\)-cut rearrangement of \((S,T)\), then \(r^{\prime}=\Psi^{p}_{X}(r)\) is an efficient \(k+p\) rearrangement of \((S^{\prime},T^{\prime})=\Phi^{p}_{X}(S,T)\). Moreover, in this case, \(r(S,T)\) is \(k\)-cyclic with sample \(X\), and \(\Phi^{p}_{X}(r(S,T))=r^{\prime}(\Phi^{p}_{X}(S,T))\). Conversely, any efficient \(k+p\) rearrangement \(r^{\prime}\) of \((S^{\prime},T^{\prime})=\Phi^{p}_{X}(S,T)\) can be written as \(r^{\prime}=\Psi^{p}_{X}(r)\), where \(r\) is an efficient \(k\)-cut rearrangement of \((S,T)\). Proof. : Given an efficient \(k\)-cut rearrangement \(r\), let  
\[(S^{0},T^{0}) =(S,T), (S^{\prime},T^{\prime}) =\phi^{p}_{x_{j}}(S^{j-1},Tj-1)\text{ for all }0<j\leq\ell,\] \[r_{0} =r, r_{j} =\psi^{p}_{x_{j}}(r_{j-1})\text{ for all }0<j\leq\ell.\]  
Since \(r\) is an efficient \(k\)-cut rearrangement of \((S,T)\) and \((S,T)\) is \(k\)-cyclic, Proposition 3 implies that \(r\) must solve a single cycle of \(\mathcal{C}(S,T)\). Let \(x\) be the representative of this cycle: \(x\) is the only breakpoint of \(X\) cut by \(r\), and \(x=x_{i}\) for some \(i\). Furthermore, \(\mathcal{C}(r(S,T))\) is also \(k\)-cyclic with sample \(X\) (with one cycle less than \(\mathcal{C}(S,T)\)). By Lemma 3, we have that \(r_{j}\) is an efficient \(k_{j}\)-cut rearrangement of \((S^{\prime},T^{\prime})\) for each \(j\), where \(k_{j}=k_{j-1}\) if \(r_{j-1}\) does not cut \(x\) (i.e., \(j\
eq i\)) and \(k_{j}=k_{j-1}+p\) otherwise. So, overall, \(r^{\prime}=r_{\ell}\) is a an efficient \((k+p)\)-cut rearrangement of \(\Phi^{p}_{X}(S,T)\). The relationship \(\Phi^{p}_{X}(r(S,T))=r^{\prime}(\Phi^{p}_{X}(S,T))\) also follows from Lemma 3. The converse direction is proven similarly using Lemma 4, with a specific attention given to the size of the rearrangements: starting from \(r^{\prime}\) (with \(k+p\) cuts), the number of cuts remains constant, except for \(\psi^{p}_{x_{j}}\), where it drops to \(k\) and then remains constant again (so the condition \(k^{\prime}\in\{k,k+p\}\) in Lemma 4 is indeed satisfied). If \((S,T)\) is \(k\)-cyclic with sample \(X\), then \((S,T)\) is \(k\)-efficiently sortable if, and only if, \(\Phi^{p}_{X}(S,T)\) is \(k\)-efficiently sortable. Proof.