Decomposition method (constraint satisfaction): Difference between revisions

Revision as of 15:21, 20 April 2006

Revision as of 14:36, 21 April 2006

Line 129:

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.

A ''pure query decomposition'' is a query decomposion in which only constraintsnodes are only associated withto nodesconstraints. From a query decomposition of a given width one can build in linearlogarithmic timespace a pure query decomposition of the same width;. thisThis is obtained by replacing the variables of a node that are not in the constraints of the node with othersome 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.