Closure properties of constraints

TLDR

Many combinatorial search problems can be expressed as constraint satisfaction problems, a class that is generally NP‑complete. The paper investigates the subclasses that arise when the possible constraint types are restricted. The authors prove that non‑NP‑complete constraint sets must satisfy an algebraic closure condition, analyze all possible forms of this condition to identify those guaranteeing tractability, and present a simple computational procedure based on an indicator problem to test a set’s closure properties. All known classes of tractable constraints over finite domains can be characterized by such an algebraic closure property.

Abstract

Many combinatorial search problems can be expressed as “constraint satisfaction problems” and this class of problems is known to be NP-complete in general. In this paper, we investigate the subclasses that arise from restricting the possible constraint types. We first show that any set of constraints that does not give rise to an NP-complete class of problems must satisfy a certain type of algebraic closure condition. We then investigate all the different possible forms of this algebraic closure property, and establish which of these are sufficient to ensure tractability. As examples, we show that all known classes of tractable constraints over finite domains can be characterized by such an algebraic closure property. Finally, we describe a simple computational procedure that can be used to determine the closure properties of a given set of constraints. This procedure involves solving a particular constraint satisfaction problem, which we call an “indicator problem.”