Pushing the frontier of minimality
Loading...
Files
Accepted Version
Date
2018-06-07
Authors
Escamocher, Guillaume
O'Sullivan, Barry
Journal Title
Journal ISSN
Volume Title
Publisher
Elsevier B.V.
Published Version
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.
Description
Keywords
Constraint satisfaction , Minimal CSP , NP-hardness result
Citation
Escamocher, G. and O'Sullivan, B. (2018) 'Pushing the frontier of minimality', Theoretical Computer Science. doi:10.1016/j.tcs.2018.06.008