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>.
===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===
[[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 <math>x_i</math> is the node associated to the bucket of <math>x_j</math>, where <math>x_j</math> is the greatest node that is in a constraint with <math>x_i</math> and precedes <math>x_i</math> in the ordering.
