---
title: "Bimodal Depth-First Search for Scalable GAC for AllDifferent"
authors:
  - "Sulian Le Bozec-Chiffoleau"
  - "Nicolas Beldiceanu"
  - "Charles Prud'homme"
  - "Gilles Simonin"
  - "Xavier Lorca"
doi: "10.24963/ijcai.2025/291"
url: "https://ijcai.org/proceedings/2025/291"
pdf: "https://ijcai.org/proceedings/2025/0291.pdf"
venue: "Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence"
year: 2025
pages: "2610-2618"
track: "Main Track"
keywords:
  - "Constraint Satisfaction and Optimization: CSO: Constraint programming"
  - "Constraint Satisfaction and Optimization: CSO: Solvers and tools"
  - "Constraint Satisfaction and Optimization: CSO: Constraint satisfaction"
---

# Bimodal Depth-First Search for Scalable GAC for AllDifferent

Sulian Le Bozec-Chiffoleau, Nicolas Beldiceanu, Charles Prud'homme, Gilles Simonin, Xavier Lorca

*Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence*, pages 2610-2618. DOI: [10.24963/ijcai.2025/291](https://doi.org/10.24963/ijcai.2025/291)

## Abstract

We propose a version of DFS designed for Constraint Programming, called bimodal DFS, that scales to both sparse and dense graphs. It runs in O(n + ~m) time, where ~m is the sum, for each vertex v, of the minimum between the numbers of successors and non-successors of v.
Integrating it into Régin’s GAC algorithm for the AllDifferent constraint results in faster performance as the problem size increases, outperforming a GPU-accelerated version.
In the vast majority of our tests, GAC now performs similarly to BC in terms of speed, but is able to solve more problems.