# Sorting by Multi-Cut Rearrangements +
## 3 Sorting by Multi-Cut Rearrangements in Permutations
### Fixed-Parameter Tractability and Approximability  
We now show that input instances with bounded \(k\) and \(\ell\) can be solved efficiently. More precisely, we show that SMCR in permutations is fixed-parameter tractable when parameterized by \(k+\ell\). In fact, SMCR admits a kernel with a polynomial size bound. []  
The kernel is based on the following reduction rule: if there is a duo \((a,b)\) (i.e., a substring \(ab\)) in both \(S\) and \(T\), then remove \(b\) from \(S\) and \(T\). Before we show the correctness, observe that the exhaustive application of the rule indeed gives the desired result: any Yes-instance that is reduced exhaustively with respect to the above rule has at most \(4k\ell+2\) letters: we must cut inside every duo in \(S\). Overall, we may create at most \(k\ell\) cuts via \(\ell\) many \(k\)-cut rearrangements. Hence, if \(S\) has more than \(k\ell\) duos, then \((S,T)\) is a NO-instance. Thus, after applying the rule exhaustively, we may replace any instance with more than \(k\ell+1\) letters in \(S\) (and thus in \(T\)) by a trivial NO-instance of constant size. Thus, the correctness of the rule remains to be proven. Consider an instance consisting of the permutations \(S\) and \(T\) to which the rule is applied and let \(S^{\prime}\) and \(T^{\prime}\) denote the resulting instance. We show that \((S,T)\) is a Yes-instance if, and only if, \((S^{\prime},T^{\prime})\) is a Yes-instance. \((\Rightarrow)\) If \((S,T)\) is a Yes-instance, then there is a sequence of \(\ell+1\) permutations \((S=S_{1},S_{2},\ldots,S_{\ell+1}=T)\), such that \(S_{i+1}\) can be obtained from \(S_{i}\) via one \(k\)-cut rearrangement. Removing \(b\) from \(S_{i}\) gives a sequence \((S^{\prime}_{1},S^{\prime}_{2},\ldots,S^{\prime}_{\ell+1}=T)\) such that \(S^{\prime}_{i+1}\) can be obtained from \(S^{\prime}_{i}\) via one \(k\)-cut rearrangement. \((\Left)\) If \((S^{\prime},T^{\prime})\) is a Yes-instance, then there is a sequence of \(\ell+1\) permutations \((S^{\prime}=S^{\prime}_{1},S^{\prime}_{2},\ldots,S^{\prime}_{\ell+1}=T^{\prime})\), such that \(S^{\prime}_{i+1}\) can be obtained from \(S^{\prime}_{i}\) via one \(k\)-cut rearrangement. Replacing \(a\) by \(ab\) in each permutation \(S^{\prime}_{i}\) gives a sequence \((S=S_{1},S_{2},\ldots,S_{\ell+1}=T)\) such that \(S^{\prime}_{i+1}\) can be obtained from \(S^{\prime}_{i}\) via one \(k\)-cut rearrangement. In addition, we show that for arbitrary values of \(k\), SMCR has a polynomial-time approximation algorithm. Let Opt-SMCR be the optimisation version of SMCR, where we look for the smallest \(\ell\) that is necessary to obtain \(T\) from \(S\) by \(k\)-cut rearrangements. **Theorem 10**. : Opt-SMCR _in permutations is 2-approximable._  
Proof. : Let \(I=(S,T,k)\) be an instance of Opt-SMCR. We first rewrite \(S\) and \(T\) into \(S^{\prime}\) and \(T^{\prime}\) in such a way that \(T^{\prime}=id_{n}\), where \(id_{n}\) denotes the identity permutation of \(\{1,\ldots,n\}\). Let \(k^{\prime}=\lfloor\frac{k}{2}\rfloor\). The algorithm consists of iterating the following three steps, starting from \(S^{\prime}\):  
1. rewrite \(S^{\prime}\), by contracting adjacencies so as to obtain a permutation containing no adjacencies,
2. cut around (i.e., right before and right after) the first \(k^{\prime}\) elements \(1,2,3,\ldots,k^{\prime}\) of that permutation, and
3. rearrange it so as to obtain \(id_{k^{\prime}}\) followed by the rest of the permutation. Steps (b) and (c) above are presented for the case where \(k\) is even. If \(k\) is odd, (b) and (c) are slightly modified, since we are left with an unused cut:  
1. do as (b) and additionally cut to the left of \(k^{\prime}+1\)
2. do as (c) but rearrange in such a way that \(k^{\prime}\) and \(k^{\prime}+1\) are consecutive. Clearly, the optimal value \(\ell\) for Opt-SMCR satisfies \(\ell\geq\frac{b(S,T)}{k}\).