You are here

Pushing the frontier of minimality

Publication Type: 
Refereed Original Article
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.
Digital Object Identifer (DOI): 
10.1016/j.tcs.2018.06.008
Publication Status: 
Published
Date Accepted for Publication: 
Monday, 4 June, 2018
Publication Date: 
12/10/2018
Journal: 
Theoretical Computer Science
Volume: 
745
Pages: 
172-201
Institution: 
National University of Ireland, Cork (UCC)
Open access repository: 
No
Publication document: