Pushing the frontier of minimality

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.