Minimum Common String Partition Parameterized by Partition Size is Fixed-Parameter Tractable

Laurent Bulteau, Christian Komusiewicz

The NP-hard Minimum Common String Partition problem asks whether two strings $x$ and $y$ can each be partitioned into at most $k$ substrings, called blocks, such that both partitio…