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 elements in the alphabet; d-MCSP, which requires the occurrence of each element to be bounded by d; and x-balanced MCSP, which requires the length of blocks being in range (n/k−x,n/k+x), where n is the length of the input strings, k is the number of blocks in the optimal common partition and x is a constant integer. 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!)2k ) 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-balanced MCSP parameterized on both k and x.
展开▼
机译：最小公用字符串分区（MCSP）由于其在基因组重排中的应用而备受关注。在本文中，我们研究了MCSP的三个变体：MCSP c ，它要求字母中最多包含c个元素； d-MCSP，它要求每个元素的出现都以d为边界；和x平衡MCSP，要求块的长度在（n / k-x，n / k + x）范围内，其中n是输入字符串的长度，k是最佳公共分区中的块数x是一个常数整数。我们证明，当c≥2时，MCSP c 是NP-hard。对于d-MCSP，我们提出了一种FPT算法，该算法在O * （（d！） 2k ）时间内运行。由于对于MCSP的一般情况是否还存在仅在k上参数化的FPT算法仍然未知，我们还针对在k和x上参数化的特殊情况x平衡MCSP设计了一种FPT算法。
展开▼
