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 several hardness of approximation results for the problem, and in the main part of the paper, we focus on devising approximation algorithms using two generic paradigms—the local-ratio technique and linear programming rounding.

Authors

• Danny Hermelin
• Dror Rawitz
• Romeo Rizzi
• Stéphane Vialette

Keywords

• Approximation algorithms
• Dictionary Generation
• Local-ratio
• Randomized rounding
• Substring Cover