Pushing the frontier of minimality

Show simple item record

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


Files in this item

Files Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record

© 2018, Elsevier B.V. All rights reserved.  This manuscript version is made available under the CC-BY-NC-ND 4.0 license. Except where otherwise noted, this item's license is described as © 2018, Elsevier B.V. All rights reserved. This manuscript version is made available under the CC-BY-NC-ND 4.0 license.
This website uses cookies. By using this website, you consent to the use of cookies in accordance with the UCC Privacy and Cookies Statement. For more information about cookies and how you can disable them, visit our Privacy and Cookies statement