# Sorting by Multi-Cut Rearrangements +
## 3 Sorting by Multi-Cut Rearrangements in Permutations
### Hardness for Constant Number of Cuts
#### 3.1.2. One-Cycle Extensions
Note that this \(2\)-cycle is tied to \(\mathcal{C}_{x}(S^{\prime},T^{\prime})\) through \((n+2,n+3)\). We now show how efficient rearrangements can be adapted through extensions. Let \(r\) be a \(k\)-cut rearrangement of \((S,T)\). We write \(r^{\prime}=\psi_{x}^{p}(r)\) for the \(k^{\prime}\)-cut rearrangement of \((S^{\prime},T^{\prime})=\phi_{x}^{p}(S,T)\) defined as follows:if \(r\) does not cut \(x\), then \(k^{\prime}=k\), \(r^{\prime}\) cuts the same elements as \(r\), and rearranges the blocks in the same order;
* if \(r\) cuts \(x\), then \(k^{\prime}=k+p\), \(r^{\prime}\) cuts the same elements as \(r\), as well as \(n+1\), \(n+2\) and \(n+3\) (when \(p=3\)), and rearranges the blocks in the same way as \(r\), with elements \(n+3\) (when \(p=3\)) and \(n+2\) inserted after \(x\). The following two lemmas show how efficient rearrangements of \((S,T)\) and those of \(\phi_{x}^{p}(S,T)\) are related through \(\psi_{x}^{p}\). Lemma 3: _If \(r\) is an efficient \(k\)-cut rearrangement of \((S,T)\), then \(r^{\prime}=\psi_{x}^{p}(r)\) is an efficient \(k^{\prime}\)-cut rearrangement of \((S^{\prime},T^{\prime})=\phi_{x}^{p}(S,T)\). Furthermore, \(r^{\prime}(S^{\prime},T^{\prime})=\phi_{x}^{p}(r(S,T))\)._  
Proof. : If \(r\) does not cut \(x\), then \(k^{\prime}=k\) and \(r^{\prime}\) solves in \((S^{\prime},T^{\prime})\) exactly the same breakpoints as \(r\), so it is efficient. Furthermore, all elements in \(r^{\prime}(S^{\prime},T^{\prime})\) and \(\phi_{x}^{p}(r(S,T))\) are in the same order as in \(r(S,T)\), except for \(n+1,\ldots,n+p\), which are inserted, in both cases, at the end of \(S\) and in \(T\) as in \(T^{\prime}\) (since \(r\) and \(r^{\prime}\) do not edit the second string). If \(r\) cuts \(x\), \(r^{\prime}\) furthermore solves breakpoints \(n+1,\ldots,n+p\), since it rearranges these elements in the same order as in \(T^{\prime}\). So, it is an efficient rearrangement as well. Finally, all elements in \(r^{\prime}(S^{\prime},T^{\prime})\) and \(\phi_{x}^{p}(r(S,T))\) are in the same order as in \(r(S,T)\), except for \(n+p,\ldots,n+2\) (which are inserted after \(x\) in both strings) and \(n+1\) (which is inserted as a last element). The following claim will be useful for proving Lemma 4. Claim 1: _Either \(r^{\prime}\) solves all breakpoints in \(\{x,n+1,\ldots,n+p\}\), or none at all._  
Proof. : For \(p=2\), this is a direct application of Proposition 3, since elements \(x\), \(n+1\) and \(n+2\) are in the same cycle of \(\mathcal{C}(S^{\prime},T^{\prime})\). For \(p=3\), by Lemma 2, \(C_{x}=\mathcal{C}_{x}(S^{\prime},T^{\prime})\) is a \((k_{x}+1)\)-cycle containing \(x\) and \(n+2\), and \(\mathcal{C}(S^{\prime},T^{\prime})\) also contains a cycle denoted \(C_{y}\) with elements \(n+1\) and \(n+3\). By Proposition 3, \(r^{\prime}\) solves any element in \(C_{x}\) (resp. \(C_{y}\)) if, and only if, it solves all elements in the same cycle (in particular, \(k^{\prime}\geq k_{x}+1\) if \(r^{\prime}\) cuts \(x\), so \(k^{\prime}=k+p\)). Furthermore, \(C_{y}\) is tied to \(C_{x}\), so if \(r^{\prime}\) solves \(C_{y}\), it must also solve \(C_{x}\) (by Proposition 4). Now, all that is left is to check the last direction: if \(r^{\prime}\) solves \(C_{x}\), then it also solves \(C_{y}\). Indeed, \(C_{x}\) is a \((k_{x}+1)\)-cycle and \(r^{\prime}\) solves a total of \(k_{x}+3\) breakpoints, so it must also solve some \(2\)-cycle \(C_{y}^{\prime}\). Aiming at a contradiction, assume that \(C_{y}^{\prime}\
eq C_{y}\). Then, \(C_{y}^{\prime}\) is already a \(2\)-cycle of \(\mathcal{C}(S,T)\), and it is tied to some other cycle \(C_{x}^{\prime}\) (both in \(\mathcal{C}(S,T)\) and \(\mathcal{C}(S^{\prime},T^{\prime})\)), so \(r^{\prime}\) also solves \(C_{x}^{\prime}\). Since \(C_{x}^{\prime}\) may not be equal to \(C_{x}\) (\(x\) was chosen without ties), \(r^{\prime}\) solves at least \(|C_{x}|+|C_{y}^{\prime}|+|C_{x}^{\prime}|>k_{x}+3\) breakpoints, which yields a contradiction for a \((k_{x}+3)\)-cut rearrangement.