The Minimum Substring Cover Problem

In this paper we consider the problem of covering a set of strings S with a set C of substrings in S, where C is said to cover S if every string in S can be written as a concatenation of the substrings in C. We discuss applications for the problem that arise in the context of computational biology and formal language theory. We then proceed to show that this problem is at least as hard as the PBMinimum Set Cover problem. In the main part of the paper, we focus on devising approximation algorithms for the problem using two generic paradigms – the local-ratio technique and linear programming rounding.