Its domains and constraints are built so to enforce a sort of equivalence to the original problem.
In particular, the domain of a variable of the dual problem contains one element for each tuple satisfying the corresponding original constraint.
Without these constraints, one dual variable may take the value corresponding to the tuple
while another dual variable takes the value corresponding to
They all enforce two values, which are tuples, to agree on one or more original variables.
The dual graph can be built directly from the original problem: it contains a vertex for each constraint, and an edge between every two constraints sharing variables; such an edge is labeled by these shared variables.
The dual problem can be solved from a join graph since all removed edges are redundant.
In turn, the problem can be solved efficiently if that join graph is a tree, using algorithms tailored for acyclic constraint satisfaction problems.
An algorithm for finding a join tree, if any, proceeds as follows.
In the first step, edges are assigned weights: if two nodes represent constraints that share
variables, the edge joining them is assigned weight
In the second step, a maximal-weight spanning tree is searched for.
Once one is found, it is checked whether it enforces the required equality of variables.
Another method for finding out whether a constraint satisfaction problem has a join tree uses the primal graph of the problem, rather than the dual graph.
The primal graph of a constraint satisfaction problem is a graph whose nodes are problem variables and whose edges represent the presence of two variables in the same constraint.
A join tree for the problem exists if: 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.
Not all constraint satisfaction problems have a join tree.
Join-tree clustering is a specific method to modify problems in such a way they acquire a joint tree.
Decomposition methods generalize join-tree clustering by grouping variables in such a way the resulting problem has a join tree.
Decomposition methods directly associate a tree with problems; the nodes of this tree are associated variables and/or constraints of the original problem.
Alternatively, one can build a binary acyclic problem directly from the decomposition tree.