# Sorting by Multi-Cut Rearrangements +
## 2 Sorting by Multi-Cut Rearrangements in Strings  
In this section, we provide algorithmic results concerning the Sorting by Multi-Cut Rearrangements problem, in the general case where \(S\) and \(T\) are strings. Our results are summarized in Table 1.  
As mentioned in the previous section, we know that SMCR is NP-hard in binary strings for \(k=3,4\)[13; 14]. In the following theorem, we extend this result to any value of \(k\), however, in larger alphabet strings. **Theorem 1**. : SMCR _is NP-hard in \(k\)-ary strings for any fixed \(k\geq 5\)._  
Proof. : By reduction from 3-Partition, a problem in which the input is a set \(\mathcal{A}\) of integers and an integer \(B\), and the question is whether \(\mathcal{A}\) can be partitioned into triples such that the integers of each triple sum up to \(B\). Observe that 3-Partition is strongly NP-hard, that is, it is NP-hard even if all integers are represented as unary numbers [17]. Given an instance of 3-Partition\((\mathcal{A},B)\) with \(\mathcal{A}=\{a_{1},a_{2},\ldots,a_{3m}\}\) and \(mB=\sum_{i=1}^{3m}a_{i}\), we construct an instance of SMCR for any fixed \(k\geq 5\) as follows. By simple padding arguments, we may assume that each \(a_{i}\) is a multiple of \(4m\) and that \(\frac{n}{4}<a_{i}<\frac{B}{2}\). This implies the following property: If for some subset \(I\) of \(\{1,2,\ldots,3m\}\) and some \(\delta\) with \(0\leq\delta\leq 4m\) we have \(\sum_{i\in I}a_{i}+\delta=B+4\), then \(\sum_{i\in I}a_{i}=B\), \(\delta=4\), and \(|I|=3\). We use a size-\(k\) alphabet \begin{table}
\begin{tabular}{|c|c|c|c|} \hline \(\ell\)\(k\) & \(O(1)\) & parameter & part of the input \\ \hline \hline \(1\) & \(\mathbb{P}\) & \(\mathsf{FPT}\) (Theorem 6) & NP-hard: \\ \hline \(O(1)\) & (Section 1.3) & & for \(\ell=1\) even when \(d=2\) (Theorem 5) \\ \hline parameter & \multicolumn{2}{c|}{_open_} & for any fixed \(\ell\geq 1\) (Theorem 4) \\ \hline part of the input & \multicolumn{2}{c|}{for any \(k\geq 5\) even in \(k\)-ary strings (Theorem 1)} \\  & \multicolumn{2}{c|}{for any odd \(k\geq 7\) even in ternary strings (Theorem 3)} \\  & \multicolumn{2}{c|}{for \(k=3\), 4 even in binary strings [13; 14]} \\ \hline \end{tabular}
\end{table} 
Table 1: Summary of the results for Sorting by Multi-Cut Rearrangements in strings. Recall that \(d\) denotes the maximum number of occurrences of any character in the input string \(S\). \(\{0,1,\ldots,k\ -\ 1\}\), we denote by \(X\) the string \(k-1\cdot k-2\cdot\ldots\cdot 3\), and by \(X^{\prime}\) the reverse of \(X\), i.e., \(3\cdot 4\cdot\ldots\cdot k-1\). Note that \(X\) and \(X^{\prime}\) have length \(k-3\geq 2\). We define  
\[S=10^{a_{1}}10^{a_{2}}\ldots 10^{a_{3m}}1(20X0X0X0)^{m}2\]  
and  
\[T=(1X^{\prime})^{3m}1(20^{B+4})^{m}2,\]  
and set \(\ell=3m\). This completes the construction. Before proving its correctness, let us group length-2 substrings of \(S\) and \(T\) (hereafter called _duos_) based on whether they are in excess in \(S\), in \(T\), or equal in both strings. * _Group 1_ contains the duos \((0,1),(1,0),(0,k-1),(k-1,k-2),\ldots,(4,3)\), and \((3,0)\), which each occur \(3m\) times in \(S\) and which do not occur in \(T\). * _Group 2_ contains the duos \((0,0)\), which occur \(Bm-3m\) times in \(S\) and \(Bm+3m\) times in \(T\), and the duos \((1,3),(3,4),\ldots,(k-2,k-1),(k-1,1)\) which do not occur in \(S\), and occur \(3m\) times each in \(T\). * _Group 3_ contains the duos \((0,2)\) and \((2,0)\), which each occur \(m\) times in \(S\) and in \(T\). There are no further duos in \(S\) or \(T\). To show the correctness of the reduction, we show that \((\mathcal{A},B)\) is a Yes-instance of 3-Partition if, and only if, there exists a sequence of at most \(\ell=3m\) many \(k\)-cut rearrangements transforming \(S\) into \(T\). \((\Rightarrow)\) Pick a solution of 3-Partition.