Minimum Common String Partition Revisited.

Minimum Common String Partition (MCSP) has drawn much attention due to its application in genome rearrangement. In this paper, we investigate three variants of MCSP: MCSP^c, which requires that there are at most c symbols in the alphabet; d-MCSP, which requires the occurrence of each symbol to be bounded by d; and x-balance MCSP, which requires the length of blocks not being x away from the average length. We show that MCSP^c is NP-hard when c ≥ 2. As for d-MCSP, we present an FPT algorithm which runs in O^*((d!)^k) time. As it is still unknown whether an FPT algorithm only parameterized on k exists for the general case of MCSP, we also devise an FPT algorithm for the special case x-balance MCSP parameterized on both k and x. [ABSTRACT FROM AUTHOR]