# Sorting by Multi-Cut Rearrangements +
## 1 Introduction
### Notations and Definitions  
Given an alphabet \(\Sigma\), let \(\Sigma^{*}\) be the set of all strings over \(\Sigma\). We say that two strings \(S,T\in\Sigma^{*}\) are _balanced_ if \(S\) and \(T\) are built on the same multiset of characters--in other words, each character in \(S\) also appears in \(T\) with the same number of occurrences. We denote by \(|S|\) the length of a string \(S\). Unless otherwise stated, we assume that \(|S|=|T|=n\). We denote by \(S_{i}\), \(1\leq i\leq n\), the \(i\)-th character of \(S\). Given a string \(S\) in \(\Sigma^{*}\), we denote by \(d\) the maximum number of occurrences of any character of \(\Sigma\) in \(S\). In the special case where \(d=1\) (i.e., when \(S\) and \(T\) are permutations), and for any \(0\leq i\leq n\), we say that there is a _breakpoint_ at position \(i\) in \(S\) (or, equivalently, that \((S_{i},S_{i+1})\) is a breakpoint) if there is no position \(0\leq j\leq n\) in \(T\), such that the two consecutive characters \(S_{i}\) and \(S_{i+1}\) are consecutive in \(T\), i.e., \(T_{j}=S_{i}\) and \(T_{j+1}=S_{i+1}\). For the special cases \(i=0\) and \(i=n\), we artificially set \(S_{0}=T_{0}=\alpha_{0}\) and \(S_{n+1}=T_{n+1}=\alpha_{n+1}\), where \(\alpha_{0}\
otin\Sigma\) and \(\alpha_{n+1}\
otin\Sigma\). Thus, there is a breakpoint at position \(0\) (resp. \(n\)) in \(S\) whenever \(S_{1}\
eq T_{1}\) (\(S_{n}\
eq T_{n}\)). We also denote by \(b(S,T)\) the number of breakpoints in \(S\) with respect to \(T\).  
**Definition 1**.: _Given a string \(S\in\Sigma^{*}\) and an integer \(k\), a \(k\)-cut rearrangement of \(S\) is an operation consisting of the two following steps: (1) cut \(S\) at \(k\) locations (thus \(S\) can be written as the concatenation of \(k+1\) strings, i.e., \(S=X_{1}\cdot X_{2}\cdot X_{3}\cdot\ldots\cdot X_{k+1}\), where any \(X_{i}\) is possibly empty, and where a cut occurs between \(X_{i}\) and \(X_{i+1}\), \(1\leq i\leq k\)) and (2) rearrange (i.e., permute) the \(X_{i}\)s, so as to obtain \(S^{\prime}=X_{\pi(1)}\cdot X_{\pi(2)}\cdot X_{\pi(3)}\cdot\ldots\cdot X_{\pi(k +1)}\), \(\pi\) being a permutation on the elements \(1,2,\ldots,k+1\), such that \(\pi(1)=1\) and \(\pi(k+1)=k+1\). Each of the \(X_{i}\)s considered in a given \(k\)-cut rearrangement will be called a block._  
In the above model, any block is only allowed to move whenever it is cut at both its left and right extremities. Hence, moving a prefix of \(S\) (resp. a suffix of \(S\)) comes at the cost of an \"extra cut\" to its left (resp. right), and this corresponds, in the above definition, to the case where \(X_{1}\) (resp. \(X_{k+1}\)) is empty.  
Note also that, although a \(k\)-cut rearrangement has been defined as a cut along \(S\) at \(k\) locations, it is always possible, if necessary, to perform only \(k^{\prime}\leq k\) cuts, by cutting several times at the same location. Thus, one may mimic a \(k\)-cut rearrangement, while actually realizing a \(k^{\prime}\)-cut rearrangement. Note finally that, in this model, each block \(X_{i}\) can only be moved, thus no reversal of \(X_{i}\) is allowed, and therefore the strings we consider are always unsigned. In this paper, we study the following problem.  
Sorting by Multi-Cut Rearrangements (SMCR)  
**Instance**: Two balanced strings \(S\) and \(T\), two integers \(k\) and \(\ell\).  
**Question**: Is there a sequence of at most \(\ell\) many \(k\)-cut rearrangements that transforms \(S\) into \(T\)?  
Some examples of \(k\)-cut rearrangement scenarii are presented in Figure 1. For convenience, we may also refer to the SMCR problem with parameters \(k\) and \(\ell\) as the \((k,\ell)\)-SMCR problem. Note that this notation shall not imply that \(k\) or \(\ell\) are constants. Unless mentioned otherwise, input strings are considered to have an unbounded alphabet, although most hardness proofs also hold for constant-size alphabets, as detailed in the tables of results.