# Sorting by Multi-Cut Rearrangements +
## 1 Introduction
### Basic Observations  
Both in permutations and strings, the cases \(k=1\) and \(k=2\) are trivial, since they do not allow one to move any block, and thus we are in the presence of a Yes-instance if, and only if, \(S=T\). Additionally, the SMCR problem is a natural generalization and extension of several problems that have already been defined and studied in the literature before, as described hereafter. When \(k=3\), each \(k\)-cut rearrangement is necessarily a transposition of blocks \(X_{2}\) and \(X_{3}\) (see Figure 2). Thus SMCR in that case is equivalent to the Sorting by Transpositions problem [2], which is NP-hard, even if \(S\) and \(T\) are permutations [12] or binary strings [13]. When \(k=4\), each \(k\)-cut rearrangement allows one to move two blocks among \(X_{2}\), \(X_{3}\) and \(X_{4}\), which exactly corresponds to the Sorting by Block Interchange problem (see Figure 2). This problem is known to be in P for permutations [3] and NP-hard for strings (an NP-hardness proof for binary strings is given in ([14], Theorem 5.7.2)). It may come as a surprise that the case \(k=4\) is polynomial on permutations, when the case \(k=3\)--and all other non-trivial cases--are NP-hard. The original algorithm for \(k=4\) is based on the cycle graph (see Section 3.1.1 for formal definitions): in this setting, the goal is to create as many cycles as possible at each step (a block interchange may create at most two cycles). The key intuition is that such an \"efficient\" block-interchange always exists and can be polynomially computed. In other words, efficient block-interchanges commute, so it is safe to greedily apply the best-available operation at any point. This is in contrast with \(k=3\), since transpositions may also create up to two new cycles, but such efficient transpositions are not always guaranteed to exist and cannot be chosen greedily (applying one may destroy another). In fact, finding a sequence of such efficient transpositions is at the core of the NP-hardness proof [12]. On a related note, [PERSON] et al. [15] proposed an algebraic formulation of the Sorting by Block Interchange problem, translating the cycles into permutation orbits, leading to a linear-time algorithm. Figure 2: Relationship between classical rearrangements and \(k\)-cut rearrangements. Cuts are represented by vertical lines, while dashed rectangles define blocks that are moved in classical rearrangements. (**a**) when \(k=3\), a \(k\)-cut rearrangement corresponds to a transposition (here of blocks \(X_{2}\) and \(X_{3}\)). (**b–f**) are the 5 possible cases that we can get with a 4-cut rearrangement, all of them corresponding to a block interchange of dashed blocks. When \(\ell=1\), the SMCR problem comes down to deciding whether \(k\) cuts are sufficient to rearrange \(S\) into \(T\) in one atomic move (i.e., one \(k\)-cut rearrangement). In permutations, the problem is trivially solved by counting the number \(b(S,T)\) of breakpoints between \(S\) and \(T\), since we have a Yes-instance if and only if \(b(S,T)\leq k\). In strings, the SMCR problem resembles the Minimum Common String Partition problem [16]. Both problems are indeed almost identical, and only differ in their optimum value, depending on whether \(S\) and \(T\) share the same prefix and/or suffix. This will be discussed in more detail in Theorems 5 and 6. When \(k\) and \(\ell\) are constant, SMCR is trivially polynomial-time solvable, since a brute-force algorithm, exhaustively testing all possible \(k\)-cut rearrangements at each of the \(\ell\) permitted moves, has a running time of \(O(n^{k\ell+1})\)--the additional factor of \(n\) being needed to verify that the result corresponds to string \(T\). It is also natural to wonder whether \((k,\ell)\)-SMCR and \((k\ell,1)\)-SMCR are equivalent. It can be easily seen that a Yes-instance for \((k,\ell)\)-SMCR is also a Yes-instance for \((k\ell,1)\)-SMCR: it suffices for this to aggregate all cuts from the \((k,\ell)\)-SMCR solution (of which there are at most \(k\ell\)), and rearrange accordingly.