Taking Advantage of Stable Sets of Variables in Constraint Satisfaction Problems

Abstract

Binary constraint satisfaction problems involve finding values for variables su bject to constraints between pairs of variables. Algorithms that t ake 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 si mpl e backtracking, but also forward checking, one of the best v ar ian ts of backtrack search. Potential applications to parallel pro cessing are noted . Some light is shed on the question of how and wh en a co n strai nt sat isfaction problem can be advantageously divided int o subproblems.