Content deleted Content added
Ligulembot (talk | contribs) migrate {{book reference}} to {{cite book}} using AWB |
→Tree decomposition: separator size |
||
Line 109:
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.
If the variables of these two nodes are <math>X_i</math> and <math>X_j</math>, the nodes on the size of <math>i</math> do not affect all variables <math>X_j</math> but only the shared variables <math>X_i \cap X_j</math>. As a result, the influence on <math>X_j</math> of the nodes on the side of <math>i</math> can be represented as a constraint on variables <math>X_i \cap X_j</math>. 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.
Line 125 ⟶ 127:
| 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 <math>n</math> may require size <math>d^n</math> to be stored, if all variables have ___domain of size <math>d</math>.
===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 <math>n_1</math> and <math>n_2</math> are two nodes to be merged and <math>N_1</math> and <math>N_2</math> are the sets of nodes joined to them, then <math>N_1 \cap N_2=\emptyset</math>, as otherwise there would be cycle in the tree. As a result, the node obtained by merging <math>n_1</math> and <math>n_2</math> will be joined to each of the nodes of <math>N_1 \cup N_2</math>. 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===
| |||