Taking Advantage of Stable Sets of Variables in Constraint Satisfaction Problems

Abstract

Binary constraint satisfaction problems involve finding values for variables subject to constraints between pairs of variables. Algorithms that take advantage of the structure of constraint connections can be more efficient than simple backtrack search. Some pairs of variables may have no direct constraint between them, even if they are linked indirectly through a chain of constraints involving other variables. A set of variables with no direct constraint between any pair of them forms a stable set in a constraint graph representation of a problem. We describe an algorithm designed to take advantage of stable sets of variables, and give experimental evidence that it can outperform not only simple backtracking, but also forward checking, one of the best variants of backtrack search. Potential applications to parallel processing are noted. Some light is shed on the question of how and when a constraint satisfaction problem can be advantageously divided