In constraint satisfaction, a decomposition method translates a constraint satisfaction problem into another constraint satisfaction problem that is binary and acyclic. 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.
Each structural restriction defined a measure of complexity of solving the problem after conversion; this measure is called width. Fixing a maximal allowed width is a way for identifying a subclass of constraint satisfaction problems. Solving problems in this class is polynomial for most decompositions; if this holds for a decomposition, the class of fixed-width problems form a tractable subclass of constraint satisfaction problems.
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 a directed 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 a binary acyclic problem; such problems can be solved in time polynomial in its size. As a result, the original problem can be solved by first translating it and then solving the resulting problem; 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 necessarily 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. Three 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.
An example constraint satisfaction problem; this problem is binary, and the constraints are represented by edges of this graph. A decomposition tree; for every edge of the original graph, there is a node that contains both its endpoints; all nodes containing a variable are connected Solving a subproblem. This example shows solving the subproblem made of all constraints on the variables of the first set . A similar procedure is done for the other sets and Each node of the tree is made a variable. Its domain is the set of solutions of the partial problem, which is a set of tuples. The constraints of the new problem allow only the tuples that contain equal values of the original variables. In the figure, equality of is shown: the corresponding constraint is only met by the first tuple of and the first tuple of , and by the second tuple of and the second tuple of . Moreover, the second tuple of cannot find a satisfied tuple in its left child (). Thus, the second tuple of should be removed.
A decomposition method 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. Of the above three conditions (tree structure, enforcement of constraints, and equivalence of copies of original variables), the first one is automatically enforced by this definition. The condition of enforcement of constraints is in mostly formulated as: the scope of each constraint is a subset of the variables of some node; however, a different condition may be used when nodes are also associated to sets of constraints. The equivalence of all copies of the original variables is usually formulated as: the subgraph induced by the nodes associated to an original variable is connected.
Decomposition methods for binary problems
A number of decomposition methods exist. Most of them generate a tractable class by bounding the width of instances. The following are the decomposition methods defined for binary constraint satisfaction problems. Since a problem can be made binary by translating it into its dual problem or using hidden variables, these methods can be indirectly used to provide a tree decomposition for arbitrary constraint satisfaction problems.
Biconnected components
In graph theory, a separating vertex is a node of a graph that "breaks" the graph when removed from it. Formally, it is a node whose removal from the graph increases the number of its connected components. A biconnected component of a graph is a maximal set of its nodes whose induced subgraph is connected and does not have any separating vertex. It is known from graph theory that the biconnected components and the separating vertices of a graph form a tree. This tree can be built as follows: its nodes are the biconnected components and the separating vertices of the graph; edges only connect a biconnected component with a separating vertex, and in particular this happens if the vertex is contained in the component. It can be proved that this graph is actually a tree.
If the constraints of a binary constraint satisfaction problem are viewed as edges of a graph whose nodes are the variables, this tree is a decomposition of the problem. The width of a decomposition is the maximal number of vertices in a biconnected component.
The primal graph of a constraint satisfaction problem (every node represents a variable and every edge a constraint between two variables) Its biconnected components (colored) and its separating vertices (black, only one in this case) The biconnected decomposition: nodes of the tree are separating vertices and biconnected components
Cycle cutset
The cycle decomposition method split a problem into a cyclic and an acyclic part. While it does not fit in the definition of the other decomposition methods, which produce a tree whose nodes are labeled with sets of nodes, it can be easily reformulated in such terms.
This decomposition method is based on the idea that, after some variables are given a value, what remains of the problem once these variables have been eliminated may be acyclic. Formally, a cycle cutset of a graph is a set of nodes that makes the graph acyclic when they are removed from it. A similar definition can be given for a constraint satisfaction problem using its primal graph. The width of a cycle decomposition is the number of variables in the cutset. The width of a problem is the minimal width of its cycle cutset decompositions.
A graph representation of a constraint satisfaction problem A cycle cutset of the graph (others exist) Removing the cycle cutset, what remains is an acyclic graph (a tree, in this case, but a forest in general)
Such a decomposition does not fit in the scheme of the other decompositions because the result of the decomposition is not a tree, but rather a set of variables (those of the cutset) and a tree (formed by the variables not in the cutset). However, a tree like those generated by the other decomposition methods can be obtained from the tree that results from removing the cutset; this is done by choosing a root, adding all variables of the cutset to all its nodes, and the variables of each node to all its children. This results in a tree whose maximal number of variables associated with a node is equal to the size of the cutset plus two. Apart from the addition of two, this is the width of the decomposition, which is defined as the number of variables in the considered cutset.
Unfortunately, determining the minimum set to remove is an NP-Hard problem.
Tree decomposition
Tree decomposition is a well-known concept from graph theory. Reformulated in terms of binary constraints, a tree decomposition is a tree whose nodes are associated to sets of variables; the scope of each constraint is contained in set of variables of some node, and the subtree of nodes associated to each variable is connected. This is the most general form of decomposition for binary constraints that follows the scheme outlined above, as the conditions imposed on the tree are only the ones that are necessary to guarantee equivalent of the original and new problem.
The width of such a decomposition is the maximal number of variables associated to the same node minus one. The treewidth of a problem is the minimal width of its tree decompositions.