# Sorting by Multi-Cut Rearrangements +
## 3 Sorting by Multi-Cut Rearrangements in Permutations
### Hardness for Constant Number of Rearrangements  
By Theorem 7, SMCR is NP-hard for constant \(k\). We now show that the case with constant \(\ell\) is NP-hard for all \(\ell\geq 2\). Since for \(\ell=1\) SMCR is the same as computing the breakpoint distance between permutations, we thus obtain a complexity dichotomy with respect to \(\ell\). **Theorem 8**: SMCR _in permutations is NP-hard for any constant \(\ell\geq 2\)._  
We refer to the notions of _breakpoint graph_, _cycles_ and _efficient rearrangements_ introduced in Section 3.1.1 of the proof of Theorem 7, as well as their first properties (Propositions 1 to 4). We first give an informal outline of our reduction for \(\ell=2\): we show that it is NP-hard to check if an input with \(2k\) breakpoints can be solved with two \(k\)-cut rearrangements (i.e., can be sorted efficiently). We build two permutations whose cycle graph can be decomposed into cycles of specific sizes, and we show that an efficient sorting scenario needs to satisfy two types of constraints: (i) each cycle must be solved entirely in the first or in the second rearrangement, so the sum of cycle size for each rearrangement must be exactly \(k\), and (ii) some cycles must satisfy precedence constraints, i.e., we generalize the notion of _ties_ by building tuples of cycles \((C_{1},\ldots,C_{p},C^{\prime})\), where some \(C_{i}\) must be solved before or during the same \(k\)-cut rearrangement as \(C^{\prime}\). We build an instance with a large cycle that needs to be solved during the first rearrangement by constraint (i), and that forces one to solve a non-trivial set of cycles in the same rearrangement by constraint (ii). Proof. : We present a reduction from Exact 3-Set Cover, where we are given a collection of sets \(\mathcal{X}=\{X_{1},X_{2},\ldots,X_{n}\}\), all of size \(3\) over a universe \(U\) of size \(3p\), and ask whether there are \(p\) sets in \(\mathcal{X}\) whose union is exactly \(U\). Further assume that \(7n=8p\). This is without loss of generality: indeed, let \(\delta=8p-7n\). If \(\delta>0\), duplicate set \(X_{1}\left\lceil\frac{\delta}{7}\right\rceil\) times, so \(n\) increases by this quantity to become \(n^{\prime}\), and \(p\) is unchanged, so \(\delta\) decreases by \(7\lceil\frac{\delta}{7}\rceil\), and now \(-7\leq 8p-7n^{\prime}\leq 0\). If \(\delta<0\), add \(3|\delta|\) new elements to the universe, and \(|\delta|\) sets to \(\mathcal{X}\), covering exactly those new elements, so both \(n\) and \(p\) increase by \(|\delta|\) and become respectively \(n_{1}\) and \(p_{1}\), yielding \(8p_{1}-7n_{1}=8p+8|\delta|-7n-7|\delta|=\delta+|\delta|=0\). The following reduction is for \(\ell=2\); we show how to extend it to any larger \(\ell\) at the end of the proof. See Figure 6 for an illustration. Given an instance of Exact 3-Set cover, we build an alphabet of size \(8n+6p+2\), with symbols \(x_{i,q}\) for \(1\leq i\leq n\) and \(1\leq q\leq 8\), and \(y_{i}\) for \(1\leq i\leq 2p+2\). Given \(u\in U\), let \(i_{1},\ldots,i_{k}\) be the indices, such that \(u\in X_{i_{j}}\) for all \(1\leq j\leq k\). Furthermore, let \(p_{j}\) be the index of \(u\) in \(X_{j}\) (i.e., 1, 2 or 3). Write \(S_{u}\) for the following string:  
\[S_{u}=x_{i_{1},2p_{1}+1}\ x_{i_{1},2p_{1}}\quad x_{i_{2},2p_{2}+1}\ x_{i_{2},2 p_{2}}\quad\cdots\quad x_{i_{k},2p_{k}+1}\ x_{i_{k},2p_{k}}.\]We now build permutations \(S\) and \(T\):  
\[S= x_{1,1}x_{1,8}\ x_{2,1}x_{2,8}\ \ldots\ x_{n,1}x_{n,8}\qquad y_{1}\ y _{4}S_{1}y_{3}\ y_{6}S_{2}y_{5}\ \ldots\ y_{6p-1}\ y_{6p+2}S_{3p}y_{6p+1}\ y_{2}\] \[T= x_{1,1}x_{1,2}\ldots x_{1,8}\ x_{2,1}x_{2,2}\ldots x_{2,8}\ \ldots\ x_{n,1}x_{n,2}\ldots x_{n,8}\qquad\qquad y_{1}\ y_{2}\ \ldots\ y_{6p+2}\]  
where the suffix of \(S\) is the concatenation of \(y_{2i-1}y_{2i+2}S_{i}\) for every \(1\leq i\leq 3p\), followed by \(y_{6p+1}y_{2}\). Finally, we set \(k=7p+1\). Note that strings \(S\) and \(T\) have \(n+1\) adjacencies (0, and each \(x_{i,8},1\leq i\leq n\)), so they have \((8n+6p+2)+1-(n+1)=7n+6p+2=14p+2=2k\) breakpoints.