Content deleted Content added
→Join graphs and join trees: how a join tree can be determined |
join-tree clustering |
||
Line 57:
In turn, chordality can be checked using a [[max-cardinality ordering]] of the variables. Such an ordering can also be used, if the two conditions above are met, for finding a join tree of the problem. Ordering constraints by their highest variable according to the ordering, an algorithm for producing a join tree proceeds from the last to the first constraint; at each step, a constraint is connected to the constraint that shares a maximal number of variables with it among the constraints that preceed it in the ordering.
==Join-tree clustering==
Not all constraint satisfaction problems have a join tree. However, problems can be modified to acquire a join tree. ''Join-tree clustering'' is a specific method, based on merging constraints, to make problem having a joint tree. Merging constraints typically increases the size of the problem, but solving a problem that has a join tree is easy for problems that have a join tree.
Since a join tree exists for a problem if and only if the primal graph of the problem is [[Chordal graph|chordal]] and it is conformat with the problem, the existence of a join tree can be obtained by modifying the problem in such a way it satisfies these two conditions. This is what join-tree clustering does. Chordality is enforced by adding new edges in the primal graph. Conformality is obtained by replacing all constraints with new 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, using an arbitrary ordering. Indeed, 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 replacing all initial constraints with new ones. 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.
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 preceeding constraint that shares more variables with it.
==Tree decomposition==
Line 75 ⟶ 93:
The maximal number of variables of the cover used by a tree decomposition is a measure of the efficiency of solving the translated problem. The minimal such measure over all possible tree decompositions of a problem is a parameter called the ''treewidth'' of that problem.
Join-tree clustering is a particular form of tree decomposition in which:
* the elements of the cover are the cliques of the graph resulting from enforcing chordality;
* the tree is the join tree;
* every constraint is assigned to all nodes of the tree whose sets of variables contain the scope of the constraint.
==See also==
| |||