Abstract
The Minimum Common String Partition (MCSP) problem is a fundamental challenge in comparative genomics used to measure evolutionary distance. While known to be NP-hard, its parameterized complexity has remained an open question for over a decade. This paper presents the first algorithm proving that MCSP is Fixed-Parameter Tractable (FPT) when parameterized solely by the partition size $k$. By employing a "guess-and-refine" strategy that manages string periodicity and uses logical "frames" to bound search spaces, the authors demonstrate that the problem can be solved in $f(k) \cdot \text{poly}(n)$ time, independent of alphabet size or character repetition.
Introduction
In bioinformatics, calculating the evolutionary distance between genomes is essential for understanding biological relationships. When genomes are represented as strings $x$ and $y$, one robust similarity metric is the Minimum Common String Partition (MCSP). The problem asks for the minimum number of pieces $k$ into which $x$ can be cut such that these pieces can be rearranged to form $y$.
Despite its conceptual simplicity, MCSP is NP-hard and difficult to approximate. Previous research identified fixed-parameter algorithms that were efficient only if both $k$ and the character repetition frequency were low. The "holy grail" of this research area was to find an algorithm that remains efficient (polynomial in string length $n$) as long as $k$ is small, regardless of the string's internal repetitions. This work finally provides that theoretical breakthrough.
Algorithmic Framework
The proposed algorithm utilizes a sophisticated "guess-and-refine" approach centered on two primary procedures: split and frames.
Approximating Block Length and the split Procedure
The algorithm avoids searching for all partition blocks simultaneously. Instead, it maintains a variable $\beta$ representing the approximate length of the longest undiscovered block, iterating through powers of two. The split procedure refines the current partition by identifying "fragile" regions—areas where a cut must exist—and breaking them into smaller segments of length approximately $\beta/3$. These segments are then matched between the two strings to narrow the search space.
The frames Procedure and Periodicity
The core innovation lies in the frames procedure. To prevent an exponential explosion in the search space, the algorithm applies six reduction rules to place "frames"—small windows within the string where a breakpoint must reside.
A significant hurdle in string algorithms is periodicity (e.g., "abababab"). High repetition creates numerous valid alignments, complicating the search for an optimal partition. The authors leverage the Fine-Wilf theorem to show that breakpoints within periodic blocks can be logically "shifted" by the period length without losing the optimal solution. This allows the algorithm to collapse massive search spaces into a manageable number of cases.
The Piece Graph
The relationship between "solid" pieces (confirmed to be cut-free) and "fragile" pieces is modeled as a bipartite graph. By analyzing the structure of this "Piece Graph"—specifically looking for degree-one vertices or cycles—the algorithm logically deduces the locations of necessary cuts.
Key Results and Theoretical Impact
The primary contribution of this work is the formal proof that MCSP is in the complexity class FPT. The paper establishes a running time of $k^{21k^2} \cdot \text{poly}(n)$. While the exponent is large—characterizing it as a "galactic algorithm" that is currently impractical for large $k$—it resolves a long-standing open question in theoretical computer science.
The result demonstrates that character repetition can be managed by focusing on the structural properties of the partition rather than the characters themselves. By identifying windows (frames) rather than exact indices, the algorithm reduces the final search to a brute-force step that is bounded only by the parameter $k$.
Conclusion and Future Directions
This paper provides the theoretical foundation for future optimizations of MCSP. While the current $k^{21k^2}$ factor is prohibitive for practical use, the authors suggest that a more efficient running time of $k^{O(k)} \cdot \text{poly}(n)$ may be achievable. Future work will also explore extending these results to "signed" MCSP, which accounts for the biological reality that DNA strands can be reversed and complemented.
Summary updated