New complexity results for the k-covers problem
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...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Conference Paper |
| Published: |
Australian Computer Society
2004
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/20.500.11937/45670 |
| _version_ | 1848757349795233792 |
|---|---|
| author | Iliopoulos, Costas Mohamed, M. Smyth, Bill |
| author2 | Peter Eades |
| author_facet | Peter Eades Iliopoulos, Costas Mohamed, M. Smyth, Bill |
| author_sort | Iliopoulos, Costas |
| building | Curtin Institutional Repository |
| collection | Online Access |
| description | 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. |
| first_indexed | 2025-11-14T09:26:41Z |
| format | Conference Paper |
| id | curtin-20.500.11937-45670 |
| institution | Curtin University Malaysia |
| institution_category | Local University |
| last_indexed | 2025-11-14T09:26:41Z |
| publishDate | 2004 |
| publisher | Australian Computer Society |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | curtin-20.500.11937-456702022-10-11T07:22:39Z New complexity results for the k-covers problem Iliopoulos, Costas Mohamed, M. Smyth, Bill Peter Eades Seokhee Hong NP-complete cover complexity string regularity 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. 2004 Conference Paper http://hdl.handle.net/20.500.11937/45670 Australian Computer Society fulltext |
| spellingShingle | NP-complete cover complexity string regularity Iliopoulos, Costas Mohamed, M. Smyth, Bill New complexity results for the k-covers problem |
| title | New complexity results for the k-covers problem |
| title_full | New complexity results for the k-covers problem |
| title_fullStr | New complexity results for the k-covers problem |
| title_full_unstemmed | New complexity results for the k-covers problem |
| title_short | New complexity results for the k-covers problem |
| title_sort | new complexity results for the k-covers problem |
| topic | NP-complete cover complexity string regularity |
| url | http://hdl.handle.net/20.500.11937/45670 |