dc.contributor.author |
Escamocher, Guillaume |
|
dc.contributor.author |
O'Sullivan, Barry |
|
dc.date.accessioned |
2018-06-13T10:52:07Z |
|
dc.date.available |
2018-06-13T10:52:07Z |
|
dc.date.issued |
2018-06-07 |
|
dc.identifier.citation |
Escamocher, G. and O'Sullivan, B. (2018) 'Pushing the frontier of minimality', Theoretical Computer Science. doi:10.1016/j.tcs.2018.06.008 |
en |
dc.identifier.issn |
0304-3975 |
|
dc.identifier.uri |
http://hdl.handle.net/10468/6287 |
|
dc.identifier.doi |
10.1016/j.tcs.2018.06.008 |
|
dc.description.abstract |
The Minimal Constraint Satisfaction Problem, or Minimal CSP for short, arises in a number of real-world applications, most notably in constraint-based product configuration. It is composed of the set of CSP problems where every allowed tuple can be extended to a solution. Despite the very restrictive structure, computing a solution to a Minimal CSP instance is NP-hard in the general case. In this paper, we look at three independent ways to add further restrictions to the problem. First, we bound the size of the domains. Second, we define the arity as a function on the number of variables. Finally we study the complexity of computing a solution to a Minimal CSP instance when not just every allowed tuple, but every partial solution smaller than a given size, can be extended to a solution. In all three cases, we show that finding a solution remains NP-hard. All these results reveal that the hardness of minimality is very robust. |
en |
dc.format.mimetype |
application/pdf |
en |
dc.language.iso |
en |
en |
dc.publisher |
Elsevier B.V. |
en |
dc.rights |
© 2018, Elsevier B.V. All rights reserved. This manuscript version is made available under the CC-BY-NC-ND 4.0 license. |
en |
dc.rights.uri |
https://creativecommons.org/licenses/by-nc-nd/4.0/ |
en |
dc.subject |
Constraint satisfaction |
en |
dc.subject |
Minimal CSP |
en |
dc.subject |
NP-hardness result |
en |
dc.title |
Pushing the frontier of minimality |
en |
dc.type |
Article (peer-reviewed) |
en |
dc.internal.authorcontactother |
Barry O'Sullivan, Computer Science, University College Cork, Cork, Ireland. +353-21-490-3000 Email: b.osullivan@cs.ucc.ie |
en |
dc.internal.availability |
Full text available |
en |
dc.check.info |
Access to this article is restricted until 24 months after publication by request of the publisher. |
en |
dc.check.date |
2020-06-07 |
|
dc.date.updated |
2018-06-13T10:20:35Z |
|
dc.description.version |
Accepted Version |
en |
dc.internal.rssid |
441409813 |
|
dc.contributor.funder |
Science Foundation Ireland
|
en |
dc.description.status |
Peer reviewed |
en |
dc.identifier.journaltitle |
Theoretical Computer Science |
en |
dc.internal.copyrightchecked |
Yes |
en |
dc.internal.licenseacceptance |
Yes |
en |
dc.internal.IRISemailaddress |
b.osullivan@cs.ucc.ie |
en |
dc.internal.bibliocheck |
In press. Check for vol. / issue / page numbers. Amend citation as necessary. |
|
dc.relation.project |
info:eu-repo/grantAgreement/SFI/SFI Research Centres/12/RC/2289/IE/INSIGHT - Irelands Big Data and Analytics Research Centre/
|
en |