# Sorting by Multi-Cut Rearrangements +
## 2 Sorting by Multi-Cut Rearrangements in Strings
Recall that the decision version of MCSP asks, given two balanced strings \(S\) and \(T\), and an integer \(p\), whether \(S\) can be written as the concatenation of \(p\) blocks \(S=X_{1}\cdot X_{2}\cdot\ldots\cdot X_{p-1}\cdot X_{p}\) and \(T\) can be written as \(T=X_{\pi(1)}\cdot X_{\pi(2)}\cdot\ldots\cdot X_{\pi(p-1)}\cdot X_{\pi(p)}\), where \(\pi\) is a permutation of \(1,2,\ldots,p\). Note that here, we may have \(\pi(1)=1\) and/or \(\pi(p)=p\). Given an instance \((S,T,p)\) of MCSP, we build an instance \((S^{\prime},T^{\prime},k,\ell)\) of SMCR by setting \(S^{\prime}=x\cdot S\), \(T^{\prime}=T\cdot x\) (with \(x\
otin\Sigma\)), \(k=p+2\) and \(\ell=1\). Clearly, if \((S,T,p)\) is a Yes-instance for MCSP, then \((S^{\prime},T^{\prime},p+2,1)\) is a Yes-instance for SMCR: the MCSP solution uses \(p-1\) cuts, to which we add one before \(x\), one after \(x\), and one after \(S\) for solving SMCR. Conversely, if \((S^{\prime},T^{\prime},k,\ell)\) is a Yes-instance for SMCR, and since \(x\) occurs only once in \(S^{\prime}\), then 2 cuts are used to \"isolate\" \(x\) from \(S^{\prime}\). Besides, since \(T^{\prime}\) ends with \(x\), there must exist a cut after the last character of \(S^{\prime}\). Hence, since \(S^{\prime}=x\cdot S\), at most \(k-3=p-1\) cuts are used strictly within \(S\), which in turns means that \(S\) has been decomposed in \(p\) blocks, which can be rearranged so as to obtain \(T\), since \(\ell=1\). Thus, \((S,T,p)\) is a Yes-instance for MCSP. Note that MCSP has been proved to be in \(\mathsf{FPT}\) with respect to the size of the solution [18]. It can be seen that this result can be adapted for the SMCR problem in the case \(\ell=1\). **Theorem 6**. : _When \(\ell=1\), SMCR is FPT with respect to parameter \(k\)._  
Proof. : Assuming \(S\
eq T\), let \(A\) (resp. \(B\)) be the length of the longest common prefix (resp. suffix) of \(S\) and \(T\). For \(0\leq a\leq A\) and \(0\leq b\leq B\), let \(S_{a,b}\) and \(T_{a,b}\) be the strings obtained from \(S\) and \(T\) by removing the first \(a\) and last \(b\) characters. Then, \(T\) can be obtained from \(S\) by one \(k\)-cut rearrangement if and only if, for some pair \((a,b)\), \(S_{a,b}\) and \(T_{a,b}\) admit a common string partition into \(k-1\) blocks. Indeed, this is easy to verify by matching the limits of the blocks in MCSP (including at the end of the strings) with the cuts of the rearrangement. So, SMCR when \(\ell=1\) can be solved using \(O(n^{2})\) calls to MCSP with parameter \(k-1\), each with a different pair \((a,b)\), which itself is \(\mathsf{FPT}\) for \(k\)[18]. Note that it is not sufficient to check only with the longest common prefix and suffix (i.e., \(S_{A,B}\) and \(T_{A,B}\)), which can be seen in the following example. When \(S=\mathsf{xxzyxty}\) and \(T=\mathsf{xxtyxzyy}\), then \(S\) can be transformed into \(T\) via the 3-cut rearrangement with the cuts \(\mathsf{x|xzy|xty}\). Moreover, we have \(A=B=2\), but only \(S_{1,1}=\mathsf{xzy}\)\(\mathsf{xty}\) and \(T_{1,1}=\mathsf{xty}\)\(\mathsf{xzy}\)have a common partition into two blocks, whereas \(S_{1,1}=\mathsf{zyxt}\) and \(T_{2,2}=\mathsf{tyxz}\) do not have such a partition.