Abstract
This seminal 1994 paper by Jean-Charles Régin introduces a powerful filtering algorithm for "all-different" constraints in Constraint Satisfaction Problems (CSPs). By leveraging bipartite matching theory, the algorithm achieves Generalized Arc-Consistency (GAC)—the maximum possible pruning—more efficiently than previous general-purpose methods. This work established the foundation for modern global constraint filtering in constraint programming.
Introduction
In Constraint Satisfaction Problems (CSPs), the goal is to assign values to variables such that all constraints are satisfied. A ubiquitous requirement is the "all-different" constraint, which specifies that a set of variables must each take a unique value from their respective domains. Traditional approaches either decomposed this into many binary "not-equal" constraints, which are computationally cheap but provide weak pruning, or used general n-ary algorithms that are too slow for large-scale problems. Régin’s algorithm provides a "middle way": maximum pruning power with a specialized, efficient graph-based implementation.
The Bipartite Value Graph
The core innovation of the paper is the representation of the "all-different" constraint as a Bipartite Value Graph. In this model, the set of nodes is partitioned into two groups: one representing the variables ($X$) and the other representing the union of all possible values in their domains ($D(X)$). An edge exists between a variable node $x_i$ and a value node $v$ if and only if $v \in D(x_i)$.
Finding a valid assignment for the variables that satisfies the "all-different" constraint is equivalent to finding a matching in this bipartite graph that covers all variable nodes. A matching is a set of edges such that no two edges share a common node.
The Filtering Algorithm
The algorithm achieves Generalized Arc-Consistency (GAC) by identifying and removing values from variable domains that cannot participate in any valid matching. The process involves three primary stages:
- Compute an Initial Maximum Matching: The algorithm first finds a maximum matching in the bipartite graph, typically using an efficient method like the Hopcroft-Karp algorithm.
- Identify Vital Edges: Using theorems from Claude Berge, the algorithm distinguishes between edges that belong to at least one maximum matching and those that do not. Edges that cannot be part of any maximum matching are "useless" for satisfying the constraint.
- Domain Pruning: Any edge $(x_i, v)$ identified as useless is removed from the graph, and the value $v$ is deleted from the domain of variable $x_i$.
To perform this identification efficiently, the undirected bipartite graph is converted into a directed graph. The algorithm then searches for Strongly Connected Components (SCCs) and alternating paths. This allows the identification of all non-matching edges in linear time relative to the number of edges in the graph.
Results and Impact
The paper demonstrates the algorithm's effectiveness using the Zebra Problem, a classic logic puzzle. Régin showed that his algorithm prunes significantly more values than standard binary arc-consistency, often reducing variable domains to single values immediately and drastically shrinking the search space.
The algorithm has a space complexity of $O(pd)$ and a time complexity of $O(p^2d^2)$ for a single constraint, where $p$ is the number of variables and $d$ is the maximum domain size. While more complex than binary checks, the massive reduction in search tree size makes it indispensable for complex combinatorial problems.
Conclusion
Régin’s work popularized the concept of "global constraints"—treating complex multi-variable relationships as single units. By bridging CSPs with combinatorial graph theory, it paved the way for a wide range of specialized filtering algorithms (e.g., for Global Cardinality constraints) that are now standard in every modern constraint solver.
Summary updated