### Citation

(PDF)
Fahiem Bacchus, Xinguang Chen, Peter van Beek, and Toby Walsh.
Binary vs. non-binary constraints.
*Artificial Intelligence*,
140:1-37, 2002.

### Abstract

There are two well known transformations from non-binary constraints
to binary constraints applicable to constraint satisfaction problems
(CSPs) with finite domains: the dual transformation and the hidden
(variable) transformation. We perform a detailed formal comparison
of these two transformations. Our comparison focuses on two
backtracking algorithms that maintain a local consistency property
at each node in their search tree: the forward checking and
maintaining arc consistency algorithms. We first compare local
consistency techniques such as arc consistency in terms of their
inferential power when they are applied to the original (non-binary)
formulation and to each of its binary transformations. For example,
we prove that enforcing arc consistency on the original formulation
is equivalent to enforcing it on the hidden transformation. We then
extend these results to the two backtracking algorithms. We are able
to give either a theoretical bound on how much one formulation is
better than another, or examples that show such a bound does not
exist. For example, we prove that the performance of the forward
checking algorithm applied to the hidden transformation of a problem
is within a polynomial bound of the performance of the same
algorithm applied to the dual transformation of the problem. Our
results can be used to help decide if applying one of these
transformations to all (or part) of a constraint satisfaction model
would be beneficial.

**Return to Publications**