Permutation-Constrained Common String Partitions with Applications

We introduce and study a new combinatorial problem based on the famous Minimum Common String Partition (MCSP) 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 \) on [k], the question is to decide whether it is possible to decompose s and t into k blocks that conform with the permutation \(\pi \). The main result of this paper is that if s and t are both d-occurrence (i.e., each letter/gene appears at most d times in s and t), then PCSP is FPT. 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 as long as the input genomes are d-occurrence.