Content deleted Content added
→Specific decomposition methods: tree clustering, copied from Constraint satisfaction dual problem |
→Specific decomposition methods: query and hypertree decomposition, rewriting of some stuff from Constraint satisfaction dual problem |
||
Line 36:
In particular, chordality is enforced by adding some "fake" binary constraints to the problem. These are binary constraints satisfied by any pair of values, and are used only to add edges to the primal graph of the problem. In particular, chordality is obtained by adding edges producing the [[Ordered graph|induced graph]] of the primal graph according to an arbitrary ordering. This procedure is correct because the induced graph is always chordal and is obtained adding edges to the original graph.
Conformality requires that the maximal cliques of the primal graph are exactly the scope of the constraints. While the scope of every original constraint is clique on the primal graph, this clique is not necessarily maximal. Moreover, even if it initially was maximal, enforcing chordality may create a larger clique. Conformality is enforced by merging constraints. In particular, for every maximal clique of the graph resulting from enforcing chordality, a new constraint with the clique as scope is created. The satisfying values of this new constraint are the ones satisfying all original constraints whose scope is contained in the clique. By this transformation, every original constraint is "included" in at least one new constraint. Indeed, the scope of every original constraint is a clique of the primal graph. This clique remains a clique even after enforcing chordality, as this process only introduces new edges. As a result, this clique either is maximal or is contained in a maximal clique.
{| cellpadding=20 style="border: thin gray solid;"
Line 48:
| The maximal cliques of the resulting graph are identified. Join-tree clustering replaces the constraints on {x3, x4, x5, x6} with two equivalent constraints, one on {x3, x4, x5} and one on {x4, x5, x6}.
|}
This translation requires the maximal cliques of a chordal graph to be identified. However, this can bone easily using the same ordering used for enforcing chordality. Since the parents of each node are all connected to each other, the maximal cliques are composed of a node (the maximal node of the clique in a max-cardinality ordering) and all its parents. As a result, these maximal cliques can be detected by considering each node with its parents.
Line 55 ⟶ 53:
The problem that results from this process has a join tree. A join tree can be obtained by using the same ordering of variables again. Proceeding from the last node to the first, every constraint is connected with the preceding constraint that shares more variables with it.
Query decomposition associates a set of variables and a set of constraints to each node of a tree; the subtree of nodes associated to a given variables and constraint is connected. The width of a decomposition is the maximal combined number of variables and constraints associated with a node.
The association of constraints with nodes, and the consequent definition of width, possibly reduces the width of decompositions. 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.
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.
A hypertree decomposition associates a set of variables and a set of constraints to each node of a tree. It extends query decomposition by allowing the constraints of a node to contain variables that are not used when creating the ___domain of the new variable associated with the node. Beside the common conditions for a decomposition method (the scope of each constraint is in at least a set of variables associated with a node and the subtree induced by an original variable is connected), the following two conditions are required to hold:
# each original variable in a node is in the scope 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 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. The variables that are not asscoiated to a node but are in the scope of the constraints of the node are "projected out" when building this instance. This can be done by first projecting the constraints over the variables of the node and then finding all solutions to this subproblem, or by first solving the subproblem with all constraints and then removing the extra variables.
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 -->
===Other decomposition methods===
* biconnected components
* hinge decomposition
* cycle cutset
* cycle hypercutset
▲* query decomposition
▲* hypertree decomposition
==References==
| |||