Introduction
Proving that a Constraint Satisfaction Problem (CSP) has no solution—known as inconsistency—is a fundamental challenge in computer science. Traditionally, solvers fall into two categories: complete methods, which perform exhaustive searches to guarantee a proof of inconsistency at high computational cost, and incomplete methods, which use local search to find solutions quickly but typically cannot prove unsatisfiability. This paper, presented at AAAI 2008, introduces the Dominance-Coloration method to bridge this gap, addressing the long-standing goal of efficiently proving CSP inconsistency without exponential-time search.
The Dominance-Coloration Method
The core innovation of this work is the transformation of a complex CSP into a simpler, "dominating" problem. A CSP $P'$ is said to dominate $P$ if the inconsistency of $P'$ implies the inconsistency of $P$. The authors leverage the "micro-structure" of a CSP—a graph where vertices represent variable-value pairs—to build this relationship.
The Iterative Algorithm
The Dominance-Coloration algorithm follows a multi-step loop to refine the problem and search for a proof of inconsistency:
- Micro-structure Generation: The algorithm first constructs the micro-structure graph of the CSP.
- Graph Coloration: Using a heuristic like DSATUR, the algorithm finds a $k$-coloration of the micro-structure. If $k$ is less than the number of variables $n$, the problem is immediately proven inconsistent.
- Mapping to Alldifferent: If $k \ge n$, the algorithm constructs a new CSP,
Alldiff(P, fk), where each variable must choose a unique color from the $k$ available colors. - Filtering and Refinement: Generalized Arc Consistency (GAC) is applied to this
Alldifferentconstraint. If GAC proves the constraint is unsatisfiable, the original CSP is inconsistent. If GAC removes specific values, these are propagated back to the original CSP, and the process repeats.
This iterative approach allows the solver to progressively simplify the problem, potentially uncovering an inconsistency that was not apparent in the initial state.
Experimental Evaluation
The method was evaluated using random CSP instances with 20 variables and a domain size of 10, varying constraint density and tightness. The researchers compared Dominance-Coloration against standard Arc Consistency (AC), Path Consistency (Path), and previous coloration-based methods.
Key Results
The Dominance-Coloration method demonstrated a significantly higher detection rate for inconsistent instances compared to other incomplete methods. Notably, its performance closely matched that of complete solvers like Forward Checking (FC) in terms of identifying unsatisfiable problems.
As shown in the performance metrics, the method remains robust in the "hard" phase transition region—the point where problems are neither trivially satisfiable nor obviously over-constrained. While previous coloration methods were only effective on very tight, over-constrained instances, this new approach maintains high detection rates across a broader spectrum of problem difficulty.
Conclusion
The Dominance-Coloration method represents a significant step forward in incomplete CSP solving. By combining graph coloring with global constraint filtering, it provides a powerful tool for proving inconsistency. Future work will focus on optimizing coloration heuristics and exploring other types of dominating constraints to further enhance the scalability and efficiency of the approach. Integration as a preprocessing step for complete solvers like MAC (Maintaining Arc Consistency) also remains a promising avenue for research.
Summary updated