Content deleted Content added
→Tree decomposition: some clarification |
other decompositions |
||
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, and <math>G=\{X_1,\ldots,X_m\}</math> is one of its covers, each <math>X_i</math> will be a variable of the new problem. Since this is not necessarily a partition, a variable of the original variable may occur in more than one <math>X_i</math>. A new problem on these variable can represent the old 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;
Line 158:
[[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 preceeds <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 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 are the scope of the constraint;
# a constraint is only associated to nodes whose original variables are included in the scope of the constraint;
# the variables of a constraints that are not variables of a 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 variables contains the scope of the constraint.
==See also==
Line 173 ⟶ 195:
| url=http://www.ics.uci.edu/~dechter/books/index.html
}} ISBN 1-55860-890-7
*{{cite book
| first=Rod
Line 183 ⟶ 204:
| url=http://www.springer.com/sgw/cda/frontpage/0,11855,5-0-22-1519914-0,00.html?referer=www.springer.de%2Fcgi-bin%2Fsearch_book.pl%3Fisbn%3D0-387-94883-X
}} ISBN 0-387-94883-X
*{{conference reference
| Author=Georg Gottlob, Nicola Leone, Francesco Scarcello
| Title=Hypertree Decompositions: A Survey
| Booktitle=MFCS 2001
| Pages=37-57
| Year=2001
| Url=http://www.springerlink.com/(rqc54x55rqwetq55eco03ymp)/app/home/contribution.asp?referrer=parent&backto=issue,5,61;journal,1765,3346;linkingpublicationresults,1:105633,1
}}
[[Category:Constraint satisfaction]]
| |||