Constraint satisfaction dual problem: Difference between revisions

Revision as of 15:17, 7 April 2006

Revision as of 15:29, 7 April 2006

Line 171:

A complete hypertree decomposition allows constraints to be associated to some nodes that do not contains all of their variables. This association is however constrained as follows:

# each constraint is associated to at least a node whose original variables areinclude the scope of the constraint;

# athe constraintoriginal isvariables onlyof associateda to nodes whose original variablesnode are includedall contained in the scope of theat least one constraint associated with the node;

# the variables of athe constraints of a node that are not variables of athe node associated to it do not occur in the subtree rooted at the node.

The first requirement preserve the equivalence of the original problem with the new one, as each constraint is enforced in some nodes of the tree and all copies of the original variables are still enforced to be all equal. On the other hand, a constraint enforced on a subset of its variables can be viewes as projected over these variables. For example, a constraint <math>A(x,y,z)</math> associated to a node <math>\{x,z\}</math> is interpreted as <math>\exists y . A(x,y,z)</math>: a pair of values satifies this constraint if there exists a satisfying extension to a value of the second argument.

The second and third requirements are not necessary to guarantee the equivalence of the original and new problem. However, they limit the number of nodes associated to a constraint.

The above is the definition of complete hypertree decompositions. A hyper-tree decomposition releases the first condition by specifying only that, for every constraint, the tree contains a node whose set of original variables contains the scope of the constraint.

==See also==