On the Decomposition of Non-binary Constraint into Equivalent Binary Constraints

Considerable research effort has been focused on the translation of non-binary CSP into an equivalent binary CSP. Most of this work has been devoted to studying the binary encoding of non-binary CSP. Three encodings have been proposed, namely dual encoding, hidden variable encoding and double encoding. Unfortunately, such encodings do not allow to use some properties and interesting results defined only for the binary case. Another approach consists in the transformation of each non-binary constraint into a set of binary constraints: the CSP obtained is called primal. Unfortunately, this transformation does not preserve satisfiability. In this paper, we propose some conditions under which a non-binary constraint can be decomposed into a set of binary constraints while preserving satisfiability. An experimental study proves that our approach is not artificial since some ternary benchmarks can be transformed into equivalent binary instances and effectively solved by MAC.