Hidden Variable Encoding

The hidden variable encoding (HVE) was inspired by the work of philosopher Peirce peirce. According to Rossi et al. rpd90, Peirce first showed that binary relations have the same expressive power as non-binary relations.

In the HVE [Rossi, Petrie, DharRossi et al.1990], the set of variables consists of all the original variables of the non-binary CSP plus the set of dual variables. As in the dual encoding, each dual variable $v_c$ corresponds to a constraint $c$ of the original problem. The domain of each dual variable consists of the tuples that satisfy the original constraint. For every dual variable $v_c$, there is a binary constraint between $v_c$ and each of the original variables $x_{i}$ such that $x_i\in vars(c)$. A tuple $\tau \in D(v_c)$ is supported in the constraint between $v_c$ and $x_i$ iff there exists a value $a\in D(x_i)$ such that $\tau[x_i]=a$.

Consider the previous example with six variables with 0-1 domains, and four constraints: $c_1:\ x_1+x_2+x_6 = 1$, $c_2:\ x_1-x_3+x_4 = 1$, $c_3:\ x_4+x_5-x_6 \geq 1$, and $c_4:\ x_2+x_5-x_6 = 0$. In the HVE there are, in addition to the original six variables, four dual variables. As in the DE, the domains of these variables are the tuples that satisfy the respective constraint. There are now compatibility constraints between a dual variable $v_c$ and the original variables contained in constraint $c$. For example, there are constraints between $v_{c_3}$ and $x_4$, between $v_{c_3}$ and $x_5$ and between $v_{c_3}$ and $x_6$, as these are the variables involved in constraint $c_3$. The compatibility constraint between $c_{v_3}$ and $x_4$ is the relation that is true iff the first element in the tuple assigned to $c_{v_3}$ equals the value of $x_4$. The HVE is shown in Figure 2.

Figure 2: Hidden variable encoding of a non-binary CSP.

=2.5in