Minimum Common String Partition Problem: Hardness and Approximations

Abstrakt

In the Minimum Common String Partition problem (MCSP) we are given two strings on input, and we wish to partition them into the same collection of substrings, minimimizing the number of the substrings in the partition. We study the complexity of the problem and describe approximations algorithms.