# 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  
We now introduce the central technical engine for the reduction of Theorem 7. Let \((S,T)\) be a pair of permutations. Let \(x\) be a vertex of \(\mathcal{C}(S,T)\) with the following properties (we say that \(x\) is _safe_): \(x\) is either an adjacency or a breakpoint without ties in a cycle of length \(k_{x}\geq 3\), and all \(2\)-cycles in \(\mathcal{C}(S,T)\) are tied. The _\(p\)-extension of \((S,T)\) on \(x\)_, with \(p\in\{2,3\}\), denoted \(\phi_{x}^{p}(S,T)\) is the pair \((S^{\prime},T^{\prime})\) such that (see Figure 5 for an example):  
* For \(p=2\): \(S^{\prime}\ =(S_{1},\ldots,S_{i}=x,n+2,S_{i+1},\ldots,S_{n},n+1)\) if \(x\) is an adjacency \(S^{\prime}\ =(S_{1},\ldots,S_{n},n+1,n+2)\) if \(x\) is a breakpoint \(T^{\prime}\ =(T_{1},\ldots,T_{j}=x,n+2,T_{j+1}=S_{i+1},\ldots,T_{n},n+1)\)
* For \(p=3\): \(S^{\prime}\ =(S_{1},\ldots,S_{i}=x,n+3,n+2,S_{i+1},\ldots,S_{n},n+1)\) if \(x\) is an adjacency \(S^{\prime}\ =(S_{1},\ldots,S_{n},n+1,n+2,n+3)\) if \(x\) is a breakpoint \(T^{\prime}\ =(T_{1},\ldots,T_{j}=x,n+3,n+2,T_{j+1}=S_{i+1},\ldots,T_{n},n+1)\)  
Note that the implicit rightmost element \(S_{n+1}=n+1\) is always inserted explicitly (indeed, \(S_{n}\) is followed by \(n+1\) in both \(S^{\prime}\) and \(T^{\prime}\)), and becomes \(S^{\prime}_{n+p+1}=T^{\prime}_{n+p+1}=n+p+1\) in the new permutations. **Lemma 2**. : _A \(p\)-extension on \(x\) has the following effects on the cycle graph:_  
* _if_ \(x\) _is an adjacency, it adds_ \(p\) _trivial cycles;_
* _if_ \(x\) _is a breakpoint and_ \(p=2\)_, it adds_ \(n+1\) _and_ \(n+2\) _to the cycle containing_ \(x\)_;_
* _if_ \(x\) _is a breakpoint and_ \(p=3\)_, it adds_ \(n+2\) _to the cycle containing_ \(x\) _and a_ \(2\)_-cycle_ \((n+1,n+3)\) _tied to the one containing_ \(x\)_._ _Other arcs and tied cycles are unchanged._  
Proof. : If \(x\) is an adjacency, the \(p\)-extension inserts elements \(n+1\) to \(n+p\) in both strings in the same order after \(x\), and they are followed by the same element in both strings, since \(x\) is an adjacency, so only trivial cycles are added. Assume now that \(x\) is a breakpoint. Consider first an arc \(T_{j}\to S_{i}\) with \(T_{j}\
eq x\) in \(\mathcal{C}(S,T)\). Since no element is inserted after \(T_{j}\) or \(S_{i}\), \(T_{j}\to S_{i}\) also appears in \(\mathcal{C}(S^{\prime},T^{\prime})\) (the case \(i=j=n\) is particular, as \(n+1\) is explicitly introduced in both sequences, but it also yields the arc \(T_{j}\to S_{j}\) in \(\mathcal{C}(S^{\prime},T^{\prime})\)). If a cycle is tied to another one through a pair \((x,y)\) in \(S\) and \((y,x)\) in \(T\), these does cannot be broken by the \(p\)-extension (since \(x\) is safe, no cycle can be tied to \(\mathcal{C}_{x}(S,T)\)), so it is still tied after the extension. Similarly, a non-tied cycle cannot become tied because of the extension. It remains to describe arcs going out from \(\{x,n+1,\ldots,n+p\}\). Let \(y\) be the head of the outgoing arc from \(x\). For \(j\) such that \(T^{\prime}_{j}=x\), we have \(T^{\prime}_{j+1}=n+p=S^{\prime}_{n+p}\), so there exists an arc \(x\to S^{\prime}_{n+p-1}=n+p-1\) in \(\mathcal{C}(S^{\prime},T^{\prime})\) (note, in particular, that \(y\) no longer has its incoming arc \(x\to y\)). For \(j\) such that \(T^{\prime}_{j}=n+1\), we have \(T^{\prime}_{j+1}=n+p+1=S^{\prime}_{n+p+1}\), so there exists an arc \(n+1\to S^{\prime}_{n+p}=n+p\) in \(\mathcal{C}(S^{\prime},T^{\prime})\). For \(p=3\) and \(j\) such that \(T^{\prime}_{j}=n+3\), we have \(T^{\prime}_{j+1}=n+2=S^{\prime}_{n+2}\), so there exists an arc \(n+3\to S^{\prime}_{n+1}=n+1\) in \(\mathcal{C}(S^{\prime},T^{\prime})\). At this point, the outgoing arcs for all vertices except \(n+2\) have been described, as well as incoming arcs for all vertices except \(y\), so the last remaining arc is \(n+2\to y\). Overall, for \(p=2\), arc \(x\to y\) is replaced with the path \(x\to n+1\to n+2\to y\). For \(p=3\), arc \(x\to y\) is replaced with \(x\to n+2\to y\) and a \(2\)-cycle \(n+1\leftrightarrow n+3\) is created.