The *dual encoding* (originally called *dual graph
encoding*) was inspired by work in relational databases. In the
dual encoding (DE) [Dechter PearlDechter Pearl1989] the variables are swapped with
constraints and vice versa. Each constraint of the original
non-binary CSP is represented by a variable which we call a *
dual variable* and denote by . We refer to the variables of
the original non-binary CSP as *original variables*. The
domain of each dual variable consists of the set of allowed
tuples in the original constraint . Binary constraints between
two dual variables and exist iff
. That is, iff the constraints and
share one or more original variables. If is the set
of original variables common to and then a tuple
is supported in the constraint between and
iff there exists a tuple
such that
.

Consider the following example with six variables with 0-1 domains, and four constraints: , , , and . The DE represents this problem with 4 dual variables, one for each constraint. The domains of these dual variables are the tuples that satisfy the respective constraint. For example, the dual variable associated with the third constraint has the domain as these are the tuples of values for which satisfy . As a second example, the dual variable associated with the last constraint has the domain . Between and there is a compatibility constraint to ensure that the two original variables in common, and , have the same values. This constraint allows only those pairs of tuples which agree on the second and third elements (i.e. for and for , or for and for ). The DE of the problem is shown in Figure 1.

In the rest of this paper, we will sometimes denote by the non-binary constraint that is encoded by dual variable . For an original variable , will denote the position of in . For instance, given a constraint on variables , .

Nikolaos Samaras 2005-11-09