Constraint satisfaction dual problem: Difference between revisions

Revision as of 13:12, 25 February 2006

Revision as of 13:38, 25 February 2006

Line 109:

A constraint satisfaction problem can be solved using one of its tree decomposition. An algorithm doing this proceeds creating constraints that are passed along the edges of the tree, from the leaves to the root and back.

The [[Image:Passing-constraint passed along an edge tells how the nodes from the originating end of the edge affect the variables of the destination node. In other words, asvg|thumb|The constraint passed from node <math>i</math> to node <math>j</math> tells howsummarizes the effects of nodes "on the "side" of <math>i</math>" constrain the variables of nodeaffect <math>j</math>.]]

In a tree, every edge breaks the graph in two parts. The constraint passed along an edge tells how the part of originating end of the edge affects the variables of the destination node. In other words, a constraint passed from node <math>i</math> to node <math>j</math> tells how the nodes "on the side of <math>i</math>" constrain the variables of node <math>j</math>.

If the variables of these two nodes are <math>X_i</math> and <math>X_j</math>, the nodes on the size of <math>i</math> do not affect all variables <math>X_j</math> but only the shared variables <math>X_i \cap X_j</math>. As a result, the influence on <math>X_j</math> of the nodes on the side of <math>i</math> can be represented as a constraint on variables <math>X_i \cap X_j</math>. Such a constraint can be seen as a "summary" of how a set of nodes affects another node.