New complexity results for the k-covers problem
The k-covers 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 3-SAT, that the k-covers problem is NP-complete. In this paper we introduce a new problem, that we call the k-bounde...
| Main Authors: | , , |
|---|---|
| Format: | Journal Article |
| Published: |
Elsevier Inc
2011
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/20.500.11937/14681 |
| _version_ | 1848748687928328192 |
|---|---|
| author | Iliopoulos, Costas Mohamed, M. Smyth, William |
| author_facet | Iliopoulos, Costas Mohamed, M. Smyth, William |
| 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 strings of 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-14T07:09:01Z |
| format | Journal Article |
| id | curtin-20.500.11937-14681 |
| institution | Curtin University Malaysia |
| institution_category | Local University |
| last_indexed | 2025-11-14T07:09:01Z |
| publishDate | 2011 |
| publisher | Elsevier Inc |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | curtin-20.500.11937-146812018-03-29T09:06:09Z New complexity results for the k-covers problem Iliopoulos, Costas Mohamed, M. Smyth, William NP-complete Complexity String Regularity Cover The k-covers 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 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. 2011 Journal Article http://hdl.handle.net/20.500.11937/14681 10.1016/j.ins.2011.02.009 Elsevier Inc restricted |
| spellingShingle | NP-complete Complexity String Regularity Cover Iliopoulos, Costas Mohamed, M. Smyth, William 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 Complexity String Regularity Cover |
| url | http://hdl.handle.net/20.500.11937/14681 |