How to convert n-ary CSP to binary CSP using dual graph transformation

Question

When I read the book -- Artificial Intelligence (a modern approach), I came across the following sentence describing the method to convert a n-ary Constraint Search Problem to a binary one:

Another way to convert an n-ary CSP to a binary one is the dual graph transformation: create a new graph in which there will be one variable for each constraint in the original graph, and one binary constraint for each pair of constraints in the original graph that share variables. For example, if the original graph has variables {X, Y, Z} and constraints ⟨(X, Y, Z), C1⟩ and ⟨(X, Y ), C2⟩ then the dual graph would have variables {C1, C2} with the binary constraint ⟨(X, Y ), R1 ⟩, where (X, Y ) are the shared variables and R1 is a new relation that defines the constraint between the shared variables, as specified by the original C1 and C2.

I don't quite get the example provided in the book, can anybody help to explain it in another way and may better provide a concrete example? thanks :D

Answer 1

Let's say your problem has the following constraints:

• C1, which involves x, y and z:
  • x + y = z
• C2, which involves x and y:
  • x < y

with the following domains:

• x :: [1,2,3]
• y :: [1,2,3]
• z :: [1,2,3]

The author says that you need to create 2 more variables, one for each constraint. They are defined as follows:

• c1 = < x, y, z >
• c2 = < x, y >

The domains of c1 and c2 are defined so that they don't violate C1 and C2, i.e.:

• c1 :: [ <1,2,3>, <2,1,3>, <1,1,2>]
• c2 :: [<1,2>, <2,3>, <1,3>]

c1 and c2 will be the nodes of the dual graph, but first you need to define a constraint between them, i.e. R1:

• R1: "the 1st and the 2nd element of c1 (x and y) must be equal to the 1st and the 2nd element of c2 respectively" (actually you could split it in two simpler constraints)