Constraint satisfaction dual problem: Difference between revisions

Revision as of 21:20, 7 April 2006

Revision as of 19:49, 10 April 2006

Line 169:

===Hypertree decomposition===

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:

# the scope of each constraint is associatedcontained toin at least aone nodeof whosethe originalsets of variables includeassociated the scope ofto the constraintnodes;

# theeach original variablesvariable ofin a node are all containedis in the scopescopes of at least one constraint associated with the node;

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

The first requirement preserve the equivalence of the original problem with the new binary one, as each constraintthat is enforcedrelative in some nodes ofto the tree. andIndeed, allit copiestells ofthat theeach original variables are still enforced to be all equal. On the other hand, a constraint enforced on a subset of its variables can be viewesenforced asin projectedsome 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 valuenodes of the second argumenttree.

The width of a tree decomposition is the maximal number of constraints associated with each node. If this width is bounded by a constant, a problem equivalent to the original one can be built in polynomial time. In particular, the constraints of a node are first projected over the variables of the node and then joined (or vice versa). For example, a constraint <math>A(x,y,z)</math> associated to a node <math>\{x,z\}</math> can be 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.

The second and third requirements of a tree decomposition are not necessary to guarantee the equivalence of the original and new problem, but are needed to ensure tractability of solving instances of bounded width, where the width of a decomposition is the maximal number of constraints associated with a node.

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==