Constraint satisfaction dual problem: Difference between revisions

Revision as of 13:53, 7 April 2006

Revision as of 14:17, 7 April 2006

Line 89:

A ''tree decomposition'' of a constraint satisfaction problem is a translation of it into a binary problem whose primal graph (the graph in which edges represent constraints) is a tree. Tree decomposition can be seen as an extension of the translation from a problem to its dual. In a dual problem, every variable represents a constraint of the original problem. This fact can be reformulated in terms of variables: each variable of the dual problem represents a set of variables of the original problem that is the scope of a constraint. Tree decomposition extends this idea by allowing sets of variables that are not the scope of any constraint.

A tree decomposition of a problem is based on a cover of the set of the original variables. If <math>X</math> is the set of the original variables, one of its coversand <math>G=\{X_1,\ldots,X_m\}</math> is needed.one Eachof its covers, each <math>X_i</math> will be a variable of the new problem. TheA followingnew areproblem requiredon forthese thevariable new problem tocan represent the originalold one if:

* <math>G</math> is a cover of <math>X</math>, that is, <math>\cup G=X</math>; it is not required that <math>G</math> is a partition; on the contrary, most partitions do not satisfy the conditions below;

* every original constraint iscan be "representedenforced" somewhere in the new problem; for this to be possible, the scope of every constraint must be contained in at least one element of <math>G</math>;

* equalityall "copies" of the original variables isare constrainted to be enforcedequal; in other words, two elements of <math>G</math> sharing a variable must be connected by a path in the new problem, and this path enforces equality of that variable; equivalently, all elements in this path contain the shared variable.

The above are sufficient conditions for building a newproblem, similar to the dual problem, that representingrepresents the original one. AThis treeproblem decompositionhas is<math>G</math> aas translationvariables, buildingand aall problemconstraints whoseare binary and enforce equality of the original variables. If the primal graph of this problem is a tree., this translation is called a ''tree decomposition''.

Formally, a tree decomposition is a translation in which every element of a cover <math>G</math> of variables is assigned a node of a tree, every constraint is assigned at least a node of that tree, and if <math>X_i</math> and <math>X_j</math> share a variable, the path between them is composed of nodes that all contain that variable. The latter condition is necessary to guarantee equality on all copies of the original variable.

The main feature of tree-decomposing a problem is that efficient algorithms for solving problems whose graph is a tree exist. However, the problem obtained by tree decomposition has size that depends on the size of the sets <math>X_i</math>. Indeed, the ___domain of <math>X_i</math> in the new problem is the set of all tuples satisfying all constraints associated to <math>X_i</math>.