|
[[Bucket elimination]] can also be reformulated as an algorithm working on a particular tree decomposition. In particular, given an ordering of the variables, every variable is associated a bucket containing all constraints such that the variable is the greatest in their scope. Bucket elimination corresponds to the tree decomposition that has a node for each bucket. This node is associated all of its constraints, and corresponds to the set of all variables of these constraints. The parent of a node associated to the bucket of <math>x_i</math> is the node associated to the bucket of <math>x_j</math>, where <math>x_j</math> is the greatest node that is in a constraint with <math>x_i</math> and precedes <math>x_i</math> in the ordering.
==Non-binary tree decompositions==
The definition of tree decomposition given above can be used for non-binary constraint satisfaction problems, but was initially defined for binary problems only. The translations defined specifically for non-binary constraints are the query decomposition and the hyper-tree decomposition. These translation specify how constraints are mapped into the nodes of the tree.
===Query decomposition===
A query decomposition of a constraint satisfaction problem is based on associating sets of constraints and variables to each node of a tree. This is similar to a tree decomposition, but the association of constraints to nodes of the tree is made explicit. In addition, it is assumed that the subtree of nodes associated to a given constraint is connected, while this assumption is not present in tree decompositions.
===Hypertree decomposition===
A 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 contained in at least one of the sets of variables associated to the nodes;
# each original variable in a node is in the scopes 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 that is relative to the tree. Indeed, it tells that each original constraint can be enforced in some nodes of the tree.
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 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.
==See also==
| 