# Sorting by Multi-Cut Rearrangements +
## 3 Sorting by Multi-Cut Rearrangements in Permutations
### Hardness for Constant Number of Rearrangements
We compute the cycles of \(\mathcal{C}(S,T)\). To this end, we describe \(n+2\) cycles  
Figure 6: Illustration of the reduction from a simplified version of Exact Cover, with size-2 sets over a size-4 universe \(U=\{1,2,3,4\}\): \(A=\{1,2\}\), \(B=\{1,4\}\), \(C=\{2,4\}\), \(D=\{3,4\}\) (for lighter indices we use \(a,b,c,d\) instead of \(x_{1},x_{2},x_{3},x_{4}\); note also that we have \(a_{i}\) for \(1\leq i\leq 6\) instead of \(1\leq i\leq 8\) because of the smaller sets). All six non-trivial cycles of \(\mathcal{C}(S,T)\) are depicted on the top permutation: \(\mathcal{C}^{a}=\{a_{1},a_{3},a_{5}\}\), \(\mathcal{C}^{b}\), etc. In this example, \((S,T)\) admits an efficient 11-cut rearrangement corresponding to an exact set cover of \(U\): cut all breakpoints in bold cycles \(\mathcal{C}^{a},\mathcal{C}^{d},\mathcal{C}^{b}_{1}\), followed by an efficient 19-cut rearrangement solving the remaining breakpoints (in the actual reduction, we consider instances where \(7n=8p\) to enforce that both efficient rearrangements have the same size \(k\)). (denoted \(C_{i}^{x}\), \(1\leq i\leq n\), \(C_{1}^{y}\) and \(C_{2}^{y}\)), and check that their total size is indeed equal to the number of breakpoints. For each \(1\leq i\leq n\), let \(C_{i}^{x}\) be cycle \(x_{i,1}\to x_{i,3}\to x_{i,5}\to x_{i,7}\to x_{i,1}\). There are \(n\) such size-\(4\) cycles, for a total size of \(4n\) breakpoints. Let \(C_{1}^{y}\) be the cycle \(y_{1}\to y_{6p+1}\to y_{6p-1}\to\ldots y_{5}\to y_{3}\to y_{1}\). It has size \(3p+1\). The remaining arcs in substring \(y_{2u+2}S_{u}y_{2u+1}\) are \(y_{2u}\to x_{i_{2},2p_{x}}\), \(x_{i_{2},2p_{y}}\to x_{i_{j-1},2p_{j-1}}\) for \(2\leq j\leq k\), and \(x_{i_{1},2p_{1}}\to y_{2u+2}\). Furthermore, \(y_{6p+2}\to y_{2}\), so all these arcs form a single cycle, \(C_{2}^{y}\) of length \(3n+3p+1\) (\(3n\) for all \(x_{i_{1},2q}\), \(q\in\{1,2,3\}\), plus \(3p+1\) for all \(y_{2q}\), \(1\leq q\leq 3p+1\)). The total size of the cycles above is \((4n)+(3p+1)+(3n+3p+1)=7n+6p+2\), so all breakpoints have been accounted for. Clearly, the reduction can be performed in polynomial time; we now prove that the reduction is correct, i.e. :  
\(S\) can be transformed into \(T\) with \(2\)\(k\)-cut rearrangements \(\Leftrightarrow\)\(\mathcal{X}\) has an exact cover of \(U\). \((\Leftarrow)\) Given an exact cover of \(U\), we show that cutting all breakpoints in cycles \(C_{1}^{y}\) and \(C_{i}^{x}\) where \(x_{i}\) is in the set cover yields a \(k\)-cut rearrangement solving \(k\) breakpoints in \(S\). In other words, we first cut the following breakpoints: for each \(i\) such that \(X_{i}\) is in the cover, cut between \(x_{i,1}\) and \(x_{i,8}\), as well as between \(x_{i,2q+1}\) and \(x_{i,2q}\) for \(1\leq q\leq 3\). Furthermore, cut after \(y_{2i+1}\) for each \(0\leq i\leq 3p\). There are indeed \(4p+3p+1=k\) cuts. At this point, each substring \(y_{2u+2}S_{u}y_{2u+1}\) is cut into two strings \(y_{2u+2}S_{u}^{u}x_{j,2p+1}\), and \(x_{j,2p}S_{u}^{\prime\prime}y_{2u+1}\) (where \(j\) is the index of the only set \(X_{j}\) in the cover, such that \(u\in X_{j}\)) merge them together in reverse order, i.e., create string \(X_{j,p}=x_{j,2p}S_{u}^{\prime\prime}y_{2u+1}y_{2u+2}S_{u}x_{i,2p+1}\) (note that breakpoint \(y_{2u+1}\) is now solved). Furthermore, we merge the prefix ending in \(y_{1}\) with \(y_{2}\), solving an additional breakpoint. Finally, for each \(j\), such that \(X_{j}\) is in the cover, insert strings \(X_{j,1}\), \(X_{j,2}\), \(X_{j,3}\) between \(x_{j,1}\) and \(x_{j,8}\). This step solves breakpoints \(x_{j,1}\), \(x_{j_{2}}\), \(x_{j_{3}}\) and \(x_{j_{3}}\) for each \(j\) in the cover, for a total of \(4p\) breakpoints solved. So, overall, \(k\) breakpoints of \(S\) can be solved with a single \(k\)-cut rearrangement. Note that the resulting \(S^{\prime}\) thus has \(k\) remaining breakpoints with \(T\): they can all be solved with a single \(k\)-cut rearrangement, so \(S\) can be sorted into \(T\) in only \(2\) steps.