Introduction
In Constraint Programming (CP), global constraints are powerful abstractions that describe complex patterns involving multiple variables, such as ensuring all variables in a set take unique values (AllDifferent). While these constraints simplify problem modeling, they introduce significant computational overhead during propagation—the process of pruning variable domains to remove values that cannot participate in a solution.
The gold standard for propagation is Generalised Arc Consistency (GAC). While GAC is computationally inexpensive for simple binary constraints, its application to global constraints can be prohibitively costly. This paper establishes a formal theoretical framework to quantify the complexity of various reasoning tasks associated with GAC.
Theoretical Framework
The authors identify and analyze five fundamental questions that arise during the enforcement of GAC:
- GACSupport: Does a specific value in a variable's domain have a "support" (a valid assignment for all other variables)?
- IsItGAC: Is the current set of domains already consistent with the constraint?
- NoGACWipeOut: Can the domains be pruned without losing all possible solutions?
- maxGAC: Is the current domain the unique, largest possible consistent subdomain?
- GACDomain: What is the specific maximal consistent subdomain?
By employing reductions from known NP-complete problems like 3-SAT and 3-Colorability, the researchers establish a hierarchy of hardness among these tasks.
As shown in the figure, these questions are deeply interconnected. A key finding is that if determining support (GACSupport) is NP-hard, then computing the final pruned domain (GACDomain) is also NP-hard.
Key Insights
The Hardness of Maximality
While many GAC tasks are NP-complete, the problem of determining if a domain is the maximal GAC subdomain (maxGAC) is categorized as $D^P$-complete. This indicates a higher level of complexity, as it requires simultaneously solving an NP problem and a co-NP problem.
The Decomposition Trap
A critical takeaway for constraint solver developers is the "decomposition trap." If a global constraint is proven NP-hard to propagate, no polynomial-time decomposition into smaller, simpler constraints can achieve the same level of pruning as GAC on the original constraint (assuming $P \neq NP$). This justifies the use of specialized, albeit complex, propagators for certain global constraints.
The Danger of Generalization
The paper highlights how tractability can be fragile. A constraint that is easy to solve when certain parameters are fixed may become NP-hard if those parameters are treated as variables. For instance, the GCC (Global Cardinality Constraint) is tractable with fixed occurrence counts but becomes intractable when those counts are themselves variables.
Results: NP-Hard Global Constraints
The research formally proves that enforcing GAC is NP-hard for several widely used global constraints, including:
- NValue: Constraints on the number of distinct values used.
- Disjoint: Ensuring two sets of variables share no common values.
- AtMost1: Ensuring set variables intersect at most once.
- ScalarProduct: Complex compositions of products within matrix models.
- Cardpath: Meta-constraints that apply a sliding window of constraints across a sequence.
These results explain why many modern solvers opt for Bounds Consistency—a weaker but faster consistency check—rather than full GAC for these specific constraints.
Conclusion and Future Work
This study provides a roadmap for understanding when to simplify constraints or settle for weaker consistency levels. However, the authors note several areas for further exploration:
- Variable Types: The current analysis is limited to finite domains. Future work is needed to extend these complexity results to set and multiset variables.
- Operational Globality: There remains a gap between theoretical NP-hardness and the "operational" definition of globality used in frameworks like Beldiceanu's graph-based models.
- Average-Case Complexity: While the worst-case complexity is high, many "intractable" constraints may still be efficiently solvable in practice using heuristics on real-world industrial instances.
Summary updated