Decomposition method (constraint satisfaction)

In constraint satisfaction, a decomposition method translates a constraint satisfaction problem into a binary acyclic one. Decomposition methods work by grouping variables into sets, and solving a subproblem for each set. These translations are done because solving binary acyclic problems is a tractable problem.

Overview

Decomposition methods translate a problem into a new one that is easier to solve. The new problem only contains binary constraints; their scopes form an acyclic graph. The variables of the new problem represent each a set of variables of the original one. These sets are not necessarily disjoint, but they cover the set of the original variables. The translation finds all partial solutions relative to each set of variables. The problem that results from the translation represents the interactions between these local solutions.

By definition, a decomposition method produces an binary acyclic problem; such problems can be solved in time polynomial in its size. The original problem can be solved by first traslating it; however, this algorithm is polynomial-time only if the decomposition does not increase size superpolynomially. The width of a decomposition method is a measure of the size of problem it produced. Originally, the width was defined as the maximal cardinality of the sets of original variables; one method, the hypertree decomposition, uses a different measure. Either way, the width of a decomposition is defined so that decompositions of size bounded by a constant do not produce excessively large problems. Instances having a decomposition of fixed width can be translated by decomposition into instances of size bounded by a polynomial in the size of the original instance.

The width of a problem is the width of its minimal-width decomposition. While decompositions of fixed width can be used to efficiently solve a problem, a bound on the width of instances does necesssarily produce a tractable structural restriction. Indeed, a fixed width problem has a decomposition of fixed width, but finding it may not be polynomial. In order for a problem of fixed width being efficiently solved by decomposition, one of its decompositions of low width has to be found efficiently. For this reason, decomposition methods and their associated width are defined in such a way not only solving the problem given a fixed-width decomposition of it is polynomial-time, but also finding a fixed width decomposition of a fixed-width problem is polynomial-time.

Decomposition methods

Decomposition methods create a problem that is easy to solve from an arbitrary one. Each variable of this new problem is associated to a set of original variables; its ___domain contains tuples of values for the variables in the associated set; in particular, these are the tuples that satisfy a set of constraints over these variables. The constraints of the new problem bounds the values of two new variables to have as values two tuples that agree on the shared original variables. Two further conditions ensure that the new problem is equivalent to the old one and can be solved efficiently.

In order for the new problem to be solvable efficiently, the primal graph of the new problem is required to be acyclic. In other words, viewing the variables as vertices and the (binary) constraints as edges, the resulting graph is required to be a tree or a forest.

In order for the new problem to be equivalent to the old one, each original constraint is enforced as part of the definition of the ___domain of at least one new variables. This requires that, for each constraint of the old problem, there exists a variable of the new problem such that its associated set of original variables include the scope of the constraint, and all tuples in its ___domain satisfy the constraint.

A further condition that is necessary to ensure equivalence is that the binary constraints are sufficient to enforce all "copies" of each original variable to assume the same value. Since the same original variable can be associated to several of the new variables, the values of these new variable must all agree on the value of the old variable. The binary constraints are used to enforce equality of the old variables shared between the two new variables. Two copies of a new variable are forced equal if there exists a path of binary constraints between their new variables and all new variables in this path contain the old variable.

A decomposition methods is usually defined by providing a tree whose nodes are the variables of the new problem; for each node, also provided are the associated set of original variables and possibly a set of original constraints used to build the ___domain of the variable in the new problem.

Specific decomposition methods

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

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

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.

Query decomposition

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.

Hypertree decomposition

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:

1. each original variable in a node is in the scope of at least one constraint associated with the node;
2. 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.

Other decomposition methods

• biconnected components
• hinge decomposition
• cycle cutset
• cycle hypercutset

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)