Abstract
The alldifferent constraint is a fundamental component of Constraint Satisfaction Problems (CSPs), requiring a set of variables to take unique values. Enforcing Generalized Arc Consistency (GAC) for this constraint is typically achieved by identifying and removing "redundant edges" in a value graph—edges that cannot belong to any maximum matching. Traditionally, this process involves computing strongly connected components (SCCs) in a residual graph, a computationally intensive task. This paper introduces a novel theorem that categorizes redundant edges into two types. We demonstrate that Type 1 redundant edges can be identified immediately following the maximum matching phase, significantly reducing the need for full SCC analysis. Our resulting algorithm demonstrates a 1- to 6-fold speedup over state-of-the-art methods across various synthetic and real-world benchmarks.
Introduction
In CSPs, the alldifferent constraint ensures that every variable in a given set is assigned a distinct value. To solve these problems efficiently, solvers use filtering algorithms to prune the search space by maintaining Generalized Arc Consistency (GAC). Since Régin’s seminal work in 1994, the standard approach has been to model the constraint as a bipartite value graph and find a maximum matching. Edges that do not participate in any maximum matching are "redundant" and can be safely removed. However, identifying these edges traditionally requires constructing a residual graph and finding its SCCs, which often becomes a performance bottleneck in large-scale applications.
Methods: Categorizing Redundant Edges
The core contribution of this work is a theoretical refinement of redundant edge identification. We classify redundant edges into two categories:
- Type 1 Redundant Edges: These edges are connected to nodes reachable via specific alternating paths from "free" (unmatched) nodes. Crucially, these can be identified "for free" using information already gathered during the maximum matching process.
- Type 2 Redundant Edges: These are the remaining redundant edges that still require SCC-based identification.
By immediately pruning Type 1 edges, our algorithm avoids building a full residual graph. Instead, it performs SCC analysis only on a significantly smaller subgraph to find any remaining Type 2 edges. This "divide and conquer" strategy minimizes the overhead associated with traditional filtering.
Key Insights and Results
The algorithm's performance was evaluated on synthetic bipartite graphs (Erdős–Rényi and Scale-free models) and a suite of real-world benchmarks from CSPLib, including the Golomb ruler, Langford’s problem, and N-Queens.
A key insight from the synthetic tests is the relationship between graph density and edge types. As shown in Figure 5, as the average degree (number of possible values per variable) increases, the proportion of Type 1 redundant edges grows. In dense graphs, Type 1 edges constitute nearly all redundant edges, allowing our algorithm to bypass almost all SCC computations.
Experimental results confirm that the new algorithm consistently outperforms the state-of-the-art, achieving speedups of 1x to 6x. On many real-world benchmarks, such as the Golomb ruler and Langford’s problem, Type 1 edges represent the vast majority of redundant edges (see Figure 6), validating the practical impact of our theoretical classification.
Conclusion
While the algorithm offers significant practical speedups, its worst-case time complexity remains $O(n^{0.5}m)$, identical to existing methods. This occurs in rare scenarios where Type 1 edges are absent. However, the empirical performance gains and memory efficiency—due to avoiding full residual graph construction—make it a superior choice for modern CSP solvers. Future research will explore applying this Type 1/Type 2 decomposition to other global constraints, potentially extending these efficiency gains to a broader class of automated reasoning problems.
Summary updated