New complexity results for the kcovers problem
Abstract
The kcovers problem (kCP) asks us to compute a minimum cardinality set of strings of given length k > 1 that covers a given string. It was shown in a recent paper, by reduction to 3SAT, that the kcovers problem is NPcomplete. In this paper we introduce a new problem, that we call the kbounded relaxed vertex cover problem (RVCPk), which we show is equivalent to kbounded set cover (SCPk). We show further that kCP is a special case of RVCPk restricted to certain classes Gx,k of graphs that represent all strings x. Thus a minimum kcover can be approximated to within a factor k in polynomial time. We discuss approximate solutions of kCP, and we state a number of conjectures and open problems related to kCP and Gx,k.
Citation
Source Title
ISSN
School
Collection
Related items
Showing items related by title, author, creator and subject.

Iliopoulos, Costas; Mohamed, M.; Smyth, Bill (2004)The kcovers problem (kCP) asks us to compute a minimum cardinality set of stringsof given length k > 1 that covers a given string. It was shown in a recent paper, by reduction to 3SAT, that the kcovers problem is ...

Kusumah, Yaya S, (2001)The facility layout design problem is concerned with determining the arrangement and configuration of facilities, which optimizes a prescribed objective such as profit, cost, or distance, and which satisfies various ...

Crochemore, M.; Iliopoulos, Costas; Pissis, S.; Tischler, G. (2010)A proper fact or u of a string y is a cover of y if every letter of y is within some occurrence of u in y. The concept generalises the notion of periods of a string. An integer array C is the minimalcover (resp. ...