Permutation-constrained Common String Partitions with Applications

We study a new combinatorial problem based on the famous Minimum Common String Partition problem, which we call Permutation-constrained Common String Partition (PCSP for short). In PCSP, we are given two sequences/genomes s and t with the same length and a permutation \(\pi \) $\pi$ on \([\ell ]\) $[\ell ]$ , the question is to decide whether it is possible to decompose s and t into \(\ell \) $\ell$ blocks that can be matched according to some specified requirements, and that conform with the permutation \(\pi \) $\pi$ . Our main result is that PCSP is FPT in parameter \(\ell + d\) $\ell +d$ , where d is the maximum number of occurrences that any symbol may have in s or t. We also study a variant where the input specifies whether each matched pair of block needs to be preserved as is, or reversed. With this result on PCSP, we show that a series of genome rearrangement problems are FPT \(k + d\) $k+d$ , where k is the rearrangement distance between two genomes of interest.