Double Encoding

The double encoding [Stergiou WalshStergiou Walsh1999] combines the hidden variable and the dual encoding. As in the HVE, the set of variables in the double encoding consists of all the variables of the original non-binary CSP plus the dual variables. For every dual variable $v_c$, there is a binary constraint between $v_c$ and each of the original variables $x_{i}$ involved in the corresponding non-binary constraint $c$. As in the DE, there are also binary constraints between two dual variables $v_c$ and $v_{c'}$ if the non-binary constraints $c$ and $c'$ share one or more original variables.