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)

Choosing the node b as the root, this is the tree similar to the ones created by the other decomposition methods

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.

Bucket elimination can 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 ${\displaystyle x_{i}}$ is the node associated to the bucket of ${\displaystyle x_{j}}$, where ${\displaystyle x_{j}}$ is the greatest node that is in a constraint with ${\displaystyle x_{i}}$ and precedes ${\displaystyle x_{i}}$ in the ordering.

Biconnected components

The biconnected decomposition of an arbitrary constraint satisfaction problem is the biconnected decomposition of its primal graph. Every constraint can be enforced on a node of the tree because each constraint creates a clique on its variables on the primal graph, and a clique is either a biconnected component or a subset of a biconnected component.

Tree decomposition

A tree decomposition of an arbitrary constraint satisfaction problem is a tree decomposition of its primal graph. Every constraint can be enforced on a node of the tree because each constraint creates a clique on its variables on the primal graph and, for every tree decomposition, the variables of a clique are completely contained in the variables of some node.

Cycle hypercutset

This is the same method of cycle cutset using the definition of cutset for hypergraphs: a cycle hypercutset of a hypergraph is a set of edges (rather than vertices) that makes the hypergraph acyclic when all their vertices are removed. A decomposition can be obtained by grouping all variables of a hypercutset in a single one. This leads to a tree whose nodes are sets of hyperedges. The width of such a decomposition is the maximal size of the sets associated with nodes, which is one if the original problem is acyclic and the size of its minimal hypercutset otherwise. The width of a problem is the minimal width of its decompositions.

Hinge decomposition

A hinge is a subset of nodes of hypergraph having some properties defined below. A hinge decomposition is based on the sets of variables that are minimal hinges of the hypergraph whose nodes are the variables of the constraint satisfaction problem and whose hyperedges are the scopes of its constraints.

The definition of hinge is as follows. Let ${\displaystyle H}$ be a set of hyperedges. A path with respect to ${\displaystyle H}$ is a sequence of edges such that the intersection of each one with the next one is non-empty and not contained in the nodes of ${\displaystyle H}$. A set of edges is connected with respect to ${\displaystyle H}$ if, for each pair of its edges, there is a path with respect to ${\displaystyle H}$ of which the two nodes are the first and the last edge. A connected component with respect to ${\displaystyle H}$ is a maximal set of connected edges with respect to ${\displaystyle H}$.

Hinges are defined for reduced hypergraphs, which are hypergraphs where no hyperedge is contained in another. A set of at least two edges ${\displaystyle H}$ is a hinge if, for every connected component ${\displaystyle F}$ with respect to ${\displaystyle H}$, all nodes in ${\displaystyle F}$ that are also in ${\displaystyle H}$ are all contained in a single edge of ${\displaystyle H}$.

A hinge decomposition is based on the correspondence between constraint satisfaction problems and hypergraphs. The hypergraph associated with a problem has the variables of the problem as nodes are the scopes of the constraints as hyperedges. A hinge decomposition of a constraint satisfaction problem is a tree whose nodes are some minimal hinges of the hypergraph associated to the problem and such that some other conditions are met. By the correspondence of problems with hypergraphs, a hinge is a set of scopes of constraints, and can therefore be considered as a set of constraints. 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. The additional condition is that, if two nodes are joined, then they share exactly one constraint, and the scope of this constraint contains all variables shared by the two nodes.

The maximal number of constraints of a node is the same for all hinge decompositions of the same problem. This number is called the degree of cyclicity of the problem or its hingewidth.

Tree clustering

Tree clustering or join-tree clustering is based on merging constraints in such a way the resulting problem has a join tree, this join tree is the result of the decomposition.

A join tree of a constraint satisfaction problem is a tree in which each node is associated a constraints (and vice versa) and such that the subtree of nodes whose constraint contains a variable is connected. As a result, producing a join tree can be viewed as a particular form of decomposition, where each node of the tree is associated the scope of a constraint.

Not all constraint satisfaction problems have a join tree. However, problems can be modified to acquire a join tree by merging constraints. 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. 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 be done 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, and such 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. Join-tree clustering can be seen as a decomposition method 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.

The width of a tree-clustering decomposition is the maximal number of variables associated with each node of the tree. The width of a problem is the minimal width of its tree-clustering decompositions.

Hinge/clustering decomposition

The result of hinge decomposition can be further simplified by decomposing each hinge using tree clustering. In other words, once the hinges have been identified, a tree clustering of each of them is produced. In terms of the resulting tree, each node is therefore replaced by a tree.

Query decomposition

Query decomposition associates a set of variables and a set of constraints to each node of a tree; each constraint is associated to some node, and the subtree induced by the nodes associated to a given variable or constraint is connected. More precisely, for each variable, the subtree of nodes associated to this variable or with a constraint having this variable in its scope is connected. The width of a decomposition is the maximal combined number of variables and constraints associated with a node.

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 hypergraph representation of a constraint satisfaction problem: the constraints are given names (P, Q, R, S, T), and their scopes are shown (P (a, b, c) means that constraint P is on the variables {a, b, c}

A query decomposition of the problem. Nodes may contain variables, constraints, or both. Although to the rightmost node are associated a total of five variables (i.e. a,b,c,d,e among the two constraints), this is a decomposition of width 3 because no node contains more than three constraints and isolated variables (there is another decomposition of width 2 and it is possible to show that this decomposition of width 2 is the minimum width of this hypergraph).

A pure query decomposition is a query decomposion in which nodes are only associated to constraints. From a query decomposition of a given width one can build in logarithmic space a pure query decomposition of the same width. This is obtained by replacing the variables of a node that are not in the constraints of the node with some constraints that contain these variables.

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

An hypertree decomposition of the same problem of the query decomposition above. R(b,d,e,-) means that the last variable of R is not a variable associated to the root. By grouping two variables in one constraint in the root, width decreases from three to two

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.

The possibility of associating a constraint with a node while some of its variables are not effectively associated with the node may produce a width that is less than query width. For example, if a node is associated to ${\displaystyle \{C(a,b),c,d,e\}}$ in a query decomposition, and a constraint ${\displaystyle D(c,d,e,f)}$ exists, a hypertree decomposition can associate the same node with constraints ${\displaystyle \{C,D\}}$ and variables ${\displaystyle \{a,b,c,d,e\}}$. Since only constraints are computed when checking width, this node has width two. The same node has width four when using query decomposition (one constraint and three variables). This width reduction is possible if two or more variables can be replaced with a single constraint, even if this constraint contains a variable that is not associated with the node.

Generalized hypertree decomposition

Generalized hypertree decompositions are defined like hypertree decompositions, but the last requirement is dropped; this is the condition "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". A problem can be clearly solved in polynomial time if a fixed-width decomposition of it is given. However, the restriction to a fixed width is not known to being tractable, as the complexity of finding a decomposition of fixed width even if one is known to exist is not known, as of 2001.

Memory/time tradeoff

The algorithm for solving a problem from a decomposition tree includes two operations: solving a subproblem relative to a node and creating the constraint relative to the shared variables (the separator) between two nodes. Different strategies can be used for these two operations. 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.)

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

For a given decomposition tree, 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 ${\displaystyle n_{1}}$ and ${\displaystyle n_{2}}$ are two nodes to be merged and ${\displaystyle N_{1}}$ and ${\displaystyle N_{2}}$ are the sets of nodes joined to them, then ${\displaystyle N_{1}\cap N_{2}=\emptyset }$, as otherwise there would be cycle in the tree. As a result, the node obtained by merging ${\displaystyle n_{1}}$ and ${\displaystyle n_{2}}$ will be joined to each of the nodes of ${\displaystyle 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.