The minimum k-cover problem

Abstract

We consider the problem of determining the minimum cardinality collection of substrings, each of given length k ≥ 2, that "cover" a given string x of length n. We describe an approach to solve this problem. This approach is based on constructing an explicit reduction from the problem to the satisfiability problem. © 2013 Anna Gorbenko and Vladimir Popov.