Minimum Common String Partition Problem: Hardness and Approximations

Abstract

In this paper we address the minimum common string partition problem. We show that even a very restricted version of the problem is NP-hard and APX-hard, and we also describe several aproximation algorithms.

Keywords

• Minimum
• Common
• String
• Partition
• Problem
• Hardness
• Approximations