Decomposition method (constraint satisfaction): Difference between revisions

Revision as of 14:31, 22 April 2006

Revision as of 14:42, 22 April 2006

Line 149:

Query decomposition associates a set of variables and a set of constraints to each node of a tree; each constraint is associated to some node, and the subtree induced by the nodes associated to a given variable or constraint is connected. More precisely, for each variable, the subtree of nodes associated to this variable or with a constraint having this variable in its scope is connected. The width of a decomposition is the maximal combined number of variables and constraints associated with a node.

TheAllowing associationconstraints ofto constraintsbe associated with nodes, and theincluding consequentconstraints in the definition of width, possiblymay reducesreduce the width of decompositionsproblems. For example, a decomposition in which all nodes are associated one constraint and a node is associated two has width 2. On the other hand, if the two constraints associated with the node have a total of ten variables, the same decomposition would have width ten at least.

Associating constraints with nodes possibly reduces the width of decompositions and of instances. On the other hand, this definition of width still allows problems of fixed width to be solved in polynomial time if the decomposition is given. In this case, the ___domain of a new variable is obtained by solving a subproblem which can be polynomially large but has a fixed number of constraints. As a result, this ___domain is guaranteed to be of polynomial size; the constraints of the new problem, being equalities of two domains, are polynomial in size as well.

{| style="border: solid thin black;"

|-

| align=center | [[Image:Query-decomposition-1.svg]]

| align=center | [[Image:Query-decomposition-2.svg]]

|-

| A hypergraph representation of a constraint satisfaction problem: the constraints are given names (P, Q, R, S, T), and their scopes are shown (P(a,b,c) means that constraint P is on the variables {a, b, c}

| A query decomposition of the problem. Nodes may contain variables, constraints, or both. Although the rightmost node is associated a total of six variables (among the two constraints), this is a decomposition of width 2 because no node contains more two between constraints and isolated variables

|}

A ''pure query decomposition'' is a query decomposion in which nodes are only associated to constraints. From a query decomposition of a given width one can build in logarithmic space a pure query decomposition of the same width. This is obtained by replacing the variables of a node that are not in the constraints of the node with some constraints that contain these variables.

A drawback of this decomposition method is that checking whether an instance has a fixed width is in general [[NP-complete]]; this has been proved to be the case with width 4.

===Hypertree decomposition===