# Sorting by Multi-Cut Rearrangements +
## 2 Sorting by Multi-Cut Rearrangements in Strings
Hence, starting from any instance \((\mathcal{A}^{\prime},B^{\prime})\) of Balanced \(p\)-Partition, we build the following instance \((S,T,k,\ell)\) of SMCR:  
\[S=10^{a^{\prime}_{1}}10^{a^{\prime}_{2}}\ldots 10^{a^{\prime}_{m}}12^{m+1}\]  
\[T=1^{pm+1}(20^{B^{\prime}})^{m}2\]  
with \(k=2p+1\) and \(\ell=m\). Clearly, \(S\) and \(T\) are built on an alphabet of cardinality \(3\). Correctness of the reduction relies on the same type of arguments, as in proof of Theorem 2, and are only informally described here: if a partition of \(\mathcal{A}^{\prime}\) exists, this provides us with a rearrangement scenario where, at each step, \(2p+1\) cuts are applied. More precisely, \(2p\) of these cuts allow one to \"disconnect\" the \(p\) blocks of the form \(0^{a^{\prime}_{i}}\) corresponding to a set \(A^{\prime}_{j}\) (of cardinality \(p\)) of the partition, while the last cut allows one to insert the concatenated abovementioned blocks into a single \(0^{B^{\prime}}\) block between two occurrences of character \(2\). The reverse direction is based on the number of duos that need to be deleted and created: there are \((2p+1)m\) duos in \(S\) which are not present in \(T\), and \((2p+1)m\) duos in \(T\) which are not present in \(S\) ; besides, \((2p+1)m=k\ell\) is the total number of cuts we are allowed altogether in a rearrangement scenario from \(S\) to \(T\). Consequently, no \((0,0)\) duo can be deleted during such a scenario, which shows that any block of the form \(0^{B^{\prime}}\) in \(T\) must be the concatenation of blocks of the form \(0^{a^{\prime}_{i}}\). This in turn proves that \(\mathcal{A}^{\prime}\) can be partitioned in sets, each of which sums to \(B^{\prime}\). Moreover, since every \(a^{\prime}_{i}>\frac{B^{\prime}}{p+1}\), all sets in that partition are of cardinality at most \(p\). However, since there are \(m\) sets and altogether \(mp\) elements to partition, we conclude that each set is necessarily of cardinality exactly \(p\). Consequently, we are in the presence of a Yes-instance for \(p\)-Partition. Theorem 3 above shows that SMCR is NP-hard for ternary strings, for any odd \(k\geq 7\). We conjecture that this result can be extended in two ways, i.e., that SMCR is NP-hard for _any_\(k\geq 5\) (both odd and even), even in the case of _binary_ strings. Theorems 1 to 3 are concerned with the complexity of SMCR relatively to parameter \(k\). We now turn our attention to parameter \(\ell\). Theorem 4: _SMCR is NP-hard for \(|\Sigma|=5\) and any fixed \(\ell\geq 1\)._Proof. : The reduction being very similar to the one of Theorem 1, we only highlight here the differences that allow us to have a fixed \(\ell\) instead of fixed \(k\). First assume that \(m\) is a multiple of \(\ell\) (add up to \(\ell\) triples of dummy elements otherwise), and let \(k=\frac{15m}{\ell}\). Note that \(k\) is a multiple of 5. The reduction is the same as in proof of Theorem 1 using \(k^{\prime}=5\) (i.e., with a size-5 alphabet). In other words, we have \(X=43\) and \(X^{\prime}=34\). In the forward direction, use the described scenario using 5-cut rearrangements, but combine a series of \(k/5\) such rearrangements into a single \(k\)-cut rearrangement, as described at the end of Section 1.3. This gives a total of \(\frac{3m}{\ell/5}=\ell\) many \(k\)-cut rearrangements sorting \(S\) into \(T\). In the reverse direction, the same breakpoint count as in proof of Theorem 1 holds, namely \(3k^{\prime}m=15m\) duos need to be broken using \(\ell\) many \(k\)-cut rearrangements, with \(\ell k=15m\). So, again, no \((0,0)\) duo may be broken, and by the same argument, we obtain a valid 3-partition of \(\mathcal{A}\). The previous theorem shows \(\mathsf{NP}\)-hardness of SMCR for any fixed \(\ell\). However, a stronger result can be obtained in the specific case \(\ell=1\). **Theorem 5**. : _SMCR is NP-hard when \(\ell=1\), even when \(d=2\)._  
Proof. : The proof is obtained by reduction from the Minimum Common String Partition (MCSP) problem, which has been proven to be \(\mathsf{NP}\)-hard in strings, even when \(d=2\)[16].