Decomposition method (constraint satisfaction)

Fixing a maximal allowed width is a way for identifying a subclass of constraint satisfaction problems.

The new problem only contains binary constraints; their scopes form a directed acyclic graph.

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.

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.

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.

This results in a tree whose maximal number of variables associated with a node is equal to the size of the cutset plus two.

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 additional conditions of the definition of a hinge decomposition are three, of which the first two ensure equivalence of the original problem with the new one.

The two conditions for equivalence are: the scope of each constraint is contained in at least one node of the tree, and the subtree induced by a variable of the original problem is connected.

Tree clustering is based on the fact that a problem has a join tree if and only if its primal graph is chordal and conformant with the problem, the latter meaning that the variables of every maximal clique of the primal graph are the scope of a constraint and vice versa.

These are binary constraints satisfied by any pair of values, and are used only to add edges to the primal graph of the problem.

Conformality requires that the maximal cliques of the primal graph are exactly the scope of the constraints.

The width of a decomposition is the maximal combined number of variables and constraints associated with a node.

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.

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 A hypertree decomposition associates a set of variables and a set of constraints to each node of a tree.

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

They are needed to guarantee that problems of bounded width can be solved in polynomial time.

Beating means that there are classes of problems that have fixed width according to a decomposition method but not according to another.

This is a polynomial-time problem, as it can be solved in polynomial time using, for example, an algorithm for enforcing directional arc consistency.

A specialized algorithm for the case of binary acyclic problems that result from a decomposition is described as follows.

It works by creating constraints that are passed along the edges of the tree, from the leaves to the root and back.

When the root is reached, the process is inverted: the summary of each node for each child is generated and sent it.

Since the separator is the intersection between two sets associated with nodes, its size cannot be larger than the induced width of the graph.

In particular, creating the constraints on separators can be done using variable elimination, which is a form of inference, while subproblems can be solved by search (backtracking, etc.)

The memory required for storing these constraints can be decreased by using a tree decomposition with small separators.

Bounding the width of a decomposition method by a constant creates a structural restriction, that is, it limits the possible scopes of constraints, but not their relations.

While most tractable structural restrictions derive from fixing the width of a decomposition method, others have been developed.