# Sorting by Multi-Cut Rearrangements +
## 3 Sorting by Multi-Cut Rearrangements in Permutations
### Hardness for Constant Number of Rearrangements
\((\Rightarrow)\) Permutation \(S\) can be sorted into \(T\) with \(\ell=2\)\(k\)-cut rearrangements if, and only if, it can be sorted using two efficient \(k\)-cut rearrangements (Proposition 1). Each of these solves a union of cycles of total size \(k\) (Proposition 3). In other words, some cycles (of total size \(k\)) are solved first (i.e., with the first rearrangement), the other cycles (of total size \(k\) as well) are solved second. Note that all cycles \(C_{i}^{x}\) together have a size of \(4n<k\), so at least one cycle among \(C_{1}^{y}\), \(C_{2}^{y}\) is solved first. They are too large to be solved together, so in fact exactly one of them is solved first, the other second. We extend the notion of being solved first to breakpoints and arcs appearing in the cycles solved first. The following result adapts Proposition 4 to our setting. **Claim 2**. : _If an arc \(u\to v\) such that \(v\) occurs before \(u\) in \(S\) is solved first, then some breakpoint strictly between \(v\) and \(u\) in \(S\) is solved first as well._  
Proof. : Let \(vw_{1}\ldots w_{k}u\) be the substring of \(S\) from \(v\) to \(u\). Then, \(T\) has \(uw_{1}\) as a consecutive pair. Solving breakpoint \(u\) implies that the rearrangement puts \(w_{1}\) just after \(u\), which is only possible if there is at least one cut point between \(w_{1}\) and \(u\) in \(S\). Consider any \(u\in U\), and element \(x_{u,3}\). This element appears in some substring \(zx_{u,3}\), \(x_{u,2}\) of \(S\) (depending on the position of \(x_{u,3}\), \(z\) is either of the form \(y_{2q}\) or \(x_{u^{\prime},2p}\)), and \(C_{2}^{y}\) has an arc \(x_{u,2}\to z\). By the lemma above, if \(C_{2}^{y}\) is solved first, then the only breakpoint between \(z\) and \(x_{u,2}\), (namely, \(x_{u,3}\)) must be solved first, and the cycle \(C_{u}^{x}\) containing it as well. So, \(C_{2}^{y}\) cannot be solved first, since otherwise, all cycles \(C^{x}\) would be solved first as well, for a total size of \(7n+3p+1>7p+1=k\). Thus, \(C_{1}^{y}\) is solved first, as well as \(\frac{k-|C_{1}^{y}|}{4}=p\) cycles of the form \(C_{i}^{x}\). Write \(P\) for the size-\(p\) subset of \(\{1,..,..,n\}\), such that \(i\in P\), if, and only if, \(C_{i}^{x}\) is solved first. We show that \(\bigcup_{i\in P}X_{i}=U\), i.e., \(P\) is a solution to the set cover instance. Indeed, let \(u\in U\). Recall that \(S\) contains substring \(y_{2u-1}y_{2u+2}S_{u}y_{2u+1}\), with arc \(y_{2u+1}\to y_{2u-1}\) in cycle \(\mathbb{C}_{1}^{q}\). Thus, some other breakpoint \(z\) of this substring must be solved first. We have \(z\
eq y_{2u+2}\) and \(z\
eq x_{i,2u}\), since otherwise \(z\in\mathbb{C}_{2}^{y}\), which is solved second. Thus \(z=x_{i,2u+1}\) for some \(i\) such that \(u\in X_{i}\), and since \(z\) is solved first, we have \(i\in P\), which concludes the hardness proof for \(\ell=2\). For higher values of \(\ell\), the following is a reduction of SMCR for \(\ell\) to SMCR for \(\ell+1\): given permutations \(S,T\) and an integer \(k\) (assuming \(S\) and \(T\) have \(k\ell\) breakpoints), let \(S^{\prime}=S\cdot z_{1}\ldots z_{k}\) and \(T^{\prime}=T\cdot z_{k}\ldots z_{1}\). Then, breakpoints \((z_{1},\ldots,z_{k})\) form a size-\(k\) cycle: any efficient sorting of \((S,T)\) must use one step to exclusively sort the breakpoints in this cycle. Thus, \((S,T)\) can be solved with \(\ell\) many \(k\)-cut rearrangements if, and only if, \((S^{\prime},T^{\prime})\) can be solved with \(\ell+1\) many \(k\)-cut rearrangements. In many settings, we encounter a class of _Center_ problems, which can be generally defined as follows: given a set of objects \(S_{1},\ldots,S_{m}\) and a radius \(k\), find an object \(S^{*}\) at distance at most \(k\) from each \(S_{i}\). In particular, in the context of strings, depending on the distance measure, this problem is called Consensus String (using the Hamming distance) or Center String (using the Edit distance).