Constraint satisfaction dual problem

The dual problem is a reformulation of a constraint satisfaction problem expressing each constraint of the original problem as a variable. Dual problems only contain binary constraints, and are therefore solvable by algorithms tailored for such problems. The join graphs and join trees of a constraint satisfaction problem are graphs representing its dual problem or a problem obtained from the dual problem removing some redundant constraints. A tree decomposition of a constraint satisfaction problem is a translation of a kind that generate problems whose representing graphs are trees.

The dual problem

The dual problem of a constraint satisfaction problem contains a variable for each constraint of the original problem. Its domains and constraints are build 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. This way, a dual variable can take a value if and only if the corresponding original constraint is satisfied by the corresponding tuple.

The constraints of the dual problem forbid two dual variables to take values that correspond to two incompatible tuples. Without these constraints, one dual variable may take the value corresponding to the tuple $x=1,y=2$ while another dual variable takes the value corresponding to $y=3,z=1$ , which assigns a different value to $y$ .

More generally, the constraints of the dual problem enforce the same values for all variables shared by two constraints. If two dual variables correspond to constraints sharing some variables, the dual problem contains a constraint between them, enforcing equality of all shared variables.

	The dual variables are the constraints of the original problem.
	The domain of each dual variable is the set of tuples of the corresponding original constraint.
	The dual constraints enforce the dual variables (original constraints) to have values (original tuples) that contain equal values of the original variables. In this example, the original constraints $C_{1}$ and $C_{2}$ share the variable $y$ . In the dual problem, the variables $C_{1}$ and $C_{2}$ are allowed to have values $(1,2)$ and $(2,1)$ because these values agree on $y=2$ .

In the dual problem, all constraints are binary. They all enforce two values, which are tuples, to agree on one or more original variables.

The dual graph is a representation of how variables are constrained in the dual problem. More precisely, the dual graph contains a node for each dual variable and an edge for every constraint between them. In addition, the edge between two variables is labeled by the original variables that are enforced equal between these two dual 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.

A dual graph. An edge between two constraints corresponds to a dual constraint enforcing equality of their shared variables. For example, the edge labeled

x,y

between

C_{1}

and

C_{2}

indicates that the dual problem contains a constraint between

C_{1}

and

C_{2}

, and this constraint enforces values (tuples) that match on

x

and

y

.

Join graphs and join trees

In the dual graph, some constraints may be unnecessary. Indeed, dual constraints enforces equality of original variables, and some constraints may be redundant because of transitivity of equality. For example, if $C_{2}$ and $C_{1}$ are joined by an edge whose label contains $y$ , and so are $C_{1}$ and $C_{3}$ , equality of $y$ in all three dual variables is guaranteed. As a result, a dual constraint between $C_{2}$ and $C_{3}$ enforcing equality of $y$ is not necessary, and could be removed if present.

Since equality of

y

is enforced by other dual constraints, the one between

C_{2}

and

C_{3}

can be dropped.

A graph obtained from the dual graph by removing some redundant edges is called a join graph. If it is a tree, it is called a join tree. 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.

Finding a join tree, if any, can be done exploiting the following property: if a dual graph has a join tree, then the maximal-weight spanning trees of the graph are all join trees, if edges are weighted by the number of variables the corresponding constraints enforce to be equal. 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 $n$ variables, the edge joining them is assigned weight $n$ . 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. If this is the case, this spanning tree is a join tree.

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:

the primal graph is chordal;
the variables of every maximal clique of the primal graph are the scope of a constraint and vice versa; this property is called conformality.

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 precede 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 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 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.


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.

Tree decomposition

A tree decomposition of a constraint satisfaction problem is a translation of it into a binary problem whose primal graph (the graph in which edges represent constraints) is a tree. Tree decomposition can be seen as an extension of the translation from a problem to its dual. In a dual problem, every variable represents a constraint of the original problem. This fact can be reformulated in terms of variables: each variable of the dual problem represents a set of variables of the original problem that is the scope of a constraint. Tree decomposition extends this idea by allowing sets of variables that are not the scope of any constraint.

A tree decomposition of a problem is based on a cover of the set of the original variables. If $X$ is the set of the original variables, and $G=\{X_{1},\ldots ,X_{m}\}$ is one of its covers, each $X_{i}$ will be a variable of the new problem. Since this is not necessarily a partition, a variable of the original variable may occur in more than one $X_{i}$ . A new problem on these variable can represent the old one if:

$G$ is a cover of $X$ , that is, $\cup G=X$ ; it is not required that $G$ is a partition; on the contrary, most partitions do not satisfy the conditions below;
every original constraint can be "enforced" somewhere in the new problem; for this to be possible, the scope of every constraint must be contained in at least one element of $G$ ;
all "copies" of the original variables are constrainted to be equal; in other words, two elements of $G$ sharing a variable must be connected by a path in the new problem, and this path enforces equality of that variable; equivalently, all elements in this path contain the shared variable.

The above are sufficient conditions for building a problem, similar to the dual problem, that represents the original one. This problem has $G$ as variables, and all constraints are binary and enforce equality of the original variables. If the primal graph of this problem is a tree, this translation is called a tree decomposition.

Formally, a tree decomposition is a translation in which every element of a cover $G$ of variables is assigned a node of a tree, every constraint is assigned at least a node of that tree, and if $X_{i}$ and $X_{j}$ share a variable, the path between them is composed of nodes that all contain that variable. The latter condition is necessary to guarantee equality on all copies of the original variable.

The main feature of tree-decomposing a problem is that efficient algorithms for solving problems whose graph is a tree exist. However, the problem obtained by tree decomposition has size that depends on the size of the sets $X_{i}$ . Indeed, the domain of $X_{i}$ in the new problem is the set of all tuples satisfying all constraints associated to $X_{i}$ .

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.

Solving from a tree decomposition

A constraint satisfaction problem can be solved using one of its tree decomposition. An algorithm doing this proceeds creating constraints that are passed along the edges of the tree, from the leaves to the root and back.

The constraint passed from node i to node j summarizes the effects of the nodes on the "side" of i to the variables of j.

In a tree, every edge breaks the graph in two parts. The constraint passed along an edge tells how the part of the originating end of the edge affects the variables of the destination node. In other words, a constraint passed from node $i$ to node $j$ tells how the nodes "on the side of $i$ " constrain the variables of node $j$ .

If the variables of these two nodes are $X_{i}$ and $X_{j}$ , the nodes on the size of $i$ do not affect all variables $X_{j}$ but only the shared variables $X_{i}\cap X_{j}$ . As a result, the influence on $X_{j}$ of the nodes on the side of $i$ can be represented as a constraint on variables $X_{i}\cap X_{j}$ . Such a constraint can be seen as a "summary" of how a set of nodes affects another node.

The algorithm proceeds from the leaves of the tree. In each node, the summaries of its children (if any) are collected. These summary and the constraint of the node are used to generate the summary of the node for its parent. When the root is reached, the process is inverted: the summary of each node for each child is generated and sent it. When all leaves are reached, the algorithm stops.


A tree decomposition with associated constraints. All variables have domain {0,..,10} in this example.	The leftmost node contains the constraint a<b and shares the variable b with its parent. These constraint allow b only to take values greater than or equal to 1. This constraint b>0 is sent to its parent.	The left child of the root receives the constraint b>0 and combines it with its constraint b<c. It shares c with its parent, and the two constraints enforce c>1. This constraint is sent to its parent.	When the root has received constraints for all its children, it combines them and sends constraints back to them. The process ends when all leaves are reached. At this point, the allowed values of variables are explicit.

The set of variables shared between two nodes is called their separator. Since the separator is the intersection between two sets associated with nodes, its size cannot be larger than the induced width of the graph.

While the width of the graph affects the time required for solving the subproblems in each node, the size of the separator affects the size of the constraints that are passed between nodes. Indeed, these constraints have the separators as scope. As a result, a constraint over a separator of size $n$ may require size $d^{n}$ to be stored, if all variables have domain of size $d$ .

Memory/time tradeoff

The algorithm for solving a problem from a tree decomposition is effecively composed of two parts: first, constraints on the separators are created and passed between nodes; second, the subproblems at each node are solved. Different strategies can be used for creating the constraints required by the first part and to solve the individual subproblems in the second part. In particular, the creating the summary constraints can be done using variable elimination, which is a form of inference, while the subproblem can be solved by search (backtracking, etc.)

A problem with this algorithm is that the constraints passed between nodes can be of size exponential in the size of the separator (the set of variables the two nodes share). The memory required for storing these constraints can be decreased by using a tree decomposition with small separators. Such tree decompositions may however have width (number of nodes in each node) larger than optimal.

For a given tree decomposition, a fixed maximal allowed separator size can be enforced by joining all pairs of nodes whose separator is larger than this size. Merging two nodes usually produces a node with an associated set of variables larger than those of the two nodes. This may increase the width of the tree. However, this merging does not change the separators of the tree other than removing the separator between the two merged nodes.

The latter is a consequence of acyclicity: two joined nodes cannot be joined to the same other node. If $n_{1}$ and $n_{2}$ are two nodes to be merged and $N_{1}$ and $N_{2}$ are the sets of nodes joined to them, then $N_{1}\cap N_{2}=\emptyset$ , as otherwise there would be cycle in the tree. As a result, the node obtained by merging $n_{1}$ and $n_{2}$ will be joined to each of the nodes of $N_{1}\cup N_{2}$ . As a result, the separators of this merged node are exactly the separators of the two original nodes.

As a result, merging a pair of nodes joined by a separator does not change the other separators. As a result, a fixed maximal separator size can be enforced by first calculating all separator sizes and then iteratively merging any pair of nodes having a separator larger than a given amount, and the size of the separators do not need to be recalculated during execution.

Separable components

In the special case of maximal separator size 1, the tree decomposition of a problem corresponds to breaking the graph of the problem in its separable components. A separation node is a node whose removal from the graph disconnects two nodes that were otherwise connected by some paths. In other words, a separation node is a point crossed by all all paths between an arbitrary pair of nodes.

A graph with no separable node is called nonseparable. There exists an algorithm that is linear in the number of edges that identifies the components of a graph that are nonseparable. Two such components share at most a node. Furthermore, viewing each component has a node and the presence of a shared variable as an edge, the nonseparable components of a graph form a tree. This tree allows for a tree decomposition where all separators have size 1. The algorithm passing constraints between nodes therefore only takes linear space, as all passed constraints have only one variable.

Reformulation

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.

Bucket elimination can also be reformulated as an algorithm working on a particular tree decomposition. In particular, given an ordering of the variables, every variable is associated a bucket containing all constraints such that the variable is the greatest in their scope. Bucket elimination corresponds to the tree decomposition that has a node for each bucket. This node is associated all of its constraints, and corresponds to the set of all variables of these constraints. The parent of a node associated to the bucket of $x_{i}$ is the node associated to the bucket of $x_{j}$ , where $x_{j}$ is the greatest node that is in a constraint with $x_{i}$ and precedes $x_{i}$ in the ordering.

References

Dechter, Rina (2003). Constraint Processing. Morgan Kaufmann. ISBN 1-55860-890-7
Downey, Rod (1997). Parameterized complexity. Springer. {{cite book}}: Unknown parameter |coauthors= ignored (|author= suggested) (help) ISBN 0-387-94883-X
Georg Gottlob, Nicola Leone, Francesco Scarcello (2001). "Hypertree Decompositions: A Survey". MFCS 2001. pp. 37–57. {{cite conference}}: Unknown parameter |booktitle= ignored (|book-title= suggested) (help)CS1 maint: multiple names: authors list (link)