On the Conversion between Non-Binary and Binary Constraint Satisfaction Problems

It is well known that any non-binary discrete constraint sat-isfaction problem (CSP) can be translated into an equivalent binary CSP. Two translations are known: the dual graph trans-lation and the hidden variable translation. However, there has been little theoretical or experimental work on how well backtracking algorithms perform on these binary representa-tions in comparison to their performance on the correspond-ing non-binary CSP. We present both theoretical and empiri-cal results to help understand the tradeoffs involved. In partic-ular, we show that translating a non-binary CSP into a binary representation can be a viable solution technique in certain circumstances. The ultimate aim of this research is to give guidance for when one should consider translating between non-binary and binary representations. Our results supply some initial answers to this question