You are here

On the Minimal Constraint Satisfaction Problem: Complexity and Generation

Publication Type: 
Refereed Conference Meeting Proceeding
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. Despite its very permissive structure, it is NP-hard, even when bounding the size of the domains by d≥9. Yet very little is known about the Minimal CSP beyond that. Our contribution through this paper is twofold. Firstly, we generalize the complexity result to any value of d. We prove that the Minimal CSP remains NP-hard for d≥3, as well as for d=2 if the arity k of the instances is strictly greater than 2. Our complexity result can be seen as providing a dichotomy theorem for the Minimal CSP. Secondly, we build a generator that can create Minimal CSP instances of any size, using the constrainedness as a parameter. Our generator can be used to study behaviors that are typical of NP-hard problems, such as the presence of a phase transition, in the case of the Minimal CSP.
Conference Name: 
COCOA 2015
Digital Object Identifer (DOI): 
10.1007/978-3-319-26626-8_54
Publication Date: 
09/12/2015
Volume: 
9486
Pages: 
731-745
Conference Location: 
United States of America
Institution: 
National University of Ireland, Cork (UCC)
Open access repository: 
Yes
Publication document: