Content deleted Content added
references + list of methods |
→Specific decomposition methods: tree clustering, copied from Constraint satisfaction dual problem |
||
Line 25:
A number of decomposition methods exist. Most of them generate a tractable class by bounding the width of instances.
===Tree clustering===
Tree clustering or join-tree clustering is based on adding fake constraints in such a way the resulting problem has a [[join tree]]. Since this change does not modify the solutions of the original problem, and a join tree can be viewed as a tree of a decomposition method, this is a decomposition method.
A join tree can be defined as the result of a decomposition method that associate each node of the tree with the scope of a constraint and vice versa. As a result of this association, each constraint can be enforced on at least one node, the one associated with it; a join tree also meets the condition that the subtree of nodes whose associated sets contain a variable is connected.
Not all constraint satisfaction problems have a join tree. However, problems can be modified to acquire a join tree by merging constraints. In particular, tree clustering is based on an equivalent condition for a problem having a join tree: a problem has a join tree if and only if its primal graph is [[Chordal graph|chordal]] and it is conformant with the problem, where a problem is conformant if the variables of every maximal clique of the primal graph are the scope of a constraint and vice versa. Tree clustering modify an arbitrary problem in such a way these two conditions are met. Chordality is enforced by adding new binary constraints. Conformality is obtained by merging constraints.
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.
{| cellpadding=20 style="border: thin gray solid;"
|-
| [[Image:Join-tree-clustering-1.svg]]
| [[Image:Join-tree-clustering-2.svg]]
| [[Image:Join-tree-clustering-3.svg]]
|-
| An example: a binary constraint satisfaction problem (join-tree clustering can also be applied to non-binary constraints.) This graph is not chordal (x3x4x5x6 form a cycle of four nodes having no chord).
| The graph is made chordal. The algorithm analyzes the nodes from x6 to x1. The red edge is the only edge added because x6 is the only node having two non-joined parents. It represents a constraint between x4 and x5 that is satisfied by every pair of values.
| 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}.
|}
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.
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.
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.
===Other decomposition methods===
* biconnected components
| |||