View Item 

New complexity results for the k-covers problem

Access Status
Open access
Authors
Iliopoulos, Costas
Mohamed, M.
Smyth, Bill
Date
2004
Type
Conference Paper

Metadata
Show full item record
Citation
Iliopoulos, Costas and Mohamed, Manal and Smyth, W. F. 2004. New complexity results for the k-covers problem, in Eades, P. and Hong, S. (ed), 15th Australian Workshop on Combinatorial Algorithms (AWOCA), pp. 141-147. Ballina, Australia: Australian Computer Society.
Source Title
Proceedings of the 15th Australian workshop on combinatorial algorithms (AWOCA)
Source Conference
15th Australian Workshop on Combinatorial Algorithms (AWOCA)
Faculty
Curtin Business School
The Digital Ecosystems and Business Intelligence Institute (DEBII)
School
Digital Ecosystems and Business Intelligence Institute (DEBII)
URI
Collection
Abstract

The k-covers 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 3-SAT, that the k-covers problem is NP-complete. In this paper we introduce a new problem, that we call the k-Bounded Relaxed Vertex Cover Problem (RVCPk), which we show is equivalent to k-Bounded 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 k-cover 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.