Scotland

We perform a detailed theoretical and empirical compari-son of the dual and hidden variable encodings of non-binary constraint satisfaction problems. We identify a simple rela-tionship between the two encodings by showing how we can translate between the two by composing or decomposing re-lations. This translation suggests that we will tend to achieve more pruning in the dual than in the hidden variable encod-ing. We prove that achieving arc-consistency on the dual encoding is strictly stronger than achieving arc-consistency on the hidden variable, and this itself is equivalent to achiev-ing generalized arc-consistency on the original (non-binary) problem. We also prove that, as a consequence of the un-usual topology of the constraint graph in the hidden variable encoding, inverse consistencies like neighborhood inverse consistency and path inverse consistency collapse down onto arc-consistency. Finally, we propose the “double encoding”, which combines together both the dual and the hidden vari-able encodings