### Dual Encoding

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 .

Figure 1: Dual encoding of a non-binary CSP.
 =2.5in
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