Decomposition method (constraint satisfaction): Difference between revisions

Revision as of 05:14, 18 December 2009

Revision as of 09:07, 8 March 2010

Line 179:

# 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 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. The variables that are not asscoiatedassociated to a node but are in the scope of the constraints of the node are "projected out" when building this instance. This can be done by first projecting the constraints over the variables of the node and then finding all solutions to this subproblem, or by first solving the subproblem with all constraints and then removing the extra variables.

[[Image:Hyphertree-decomposition.svg|right|frame|An hypertree decomposition of the same problem of the query decomposition above. R(b,d,e,-) means that the last variable of R is not a variable associated to the root. By grouping two variables in one constraint in the root, width decreases from three to two]]