Content deleted Content added
→Hypertree decomposition: width reduction |
→Hypertree decomposition: image |
||
Line 177:
The two requirements above are not necessary to guarantee the equivalence of the original and new problem. They are needed to guarantee that problems of bounded width can be solved in polynomial time. <!-- In particular, the first condition guarantees that the new problem can be built in polynomial time, while the second guarantees that finding a decomposition of fixed with can be done in polynomial time if one exists -->
[[Image:Hypertree-decomposition.svg|right|frame|An hypertree decomposition of the same problem of the query decomposition above. By grouping two variables in one constraint in the root, width decreases from three to two]]
The possibility of associating a constraint with a node while some of its variables are not effectively associated with the node may produce a width that is less than query width. For example, if a node is associated to <math>\{C(a,b),c,d,e\}</math> in a query decomposition, and a constraint <math>D(c,d,e,f)</math> exists, a hypertree decomposition can associate the same node with constraints <math>\{C,D\}</math> and variables <math>\{a,b,c,d,e\}</math>. Since only constraints are computed when checking width, this node has width two. The same node has width four when using query decomposition (one constraint and three variables). This width reduction is possible if two or more variables can be replaced with a single constraint, even if this constraint contains a variable that is not associated with the node.
| |||