are not consistent with each other. There are two cases in which this does not happen, and directional consistency guarantees satisfiability if no domain is empty and no constraint is unsatisfiable. The first case is that of a binary constraint problem with an ordering of the variables that makes the ordered graph of constraint having width 1. Such an ordering exists if and only if the graph of constraints is a tree. If this is the case, the width of the graph bounds the maximal number of lower (according to the ordering) nodes a node is joined to. Directional arc consistency guarantees that every consistent assignment to a variable can be extended to higher nodes, and width 1 guarantees that a node is not joined to more than one lower node. As a result, once the lower variable is assigned, its value can be consistently extended to every higher variable it is joined with. This extension cannot later lead to inconsistency. Indeed, no other lower variable is joined to that higher variable, as the graph has width 1. As a result, if a constraint problem has width 1 with respect to an ordering of its variables (which implies that its corresponding graph is a tree) and the problem is directionally arc consistent with respect to the same ordering, a solution (if any) can be found by iteratively assigning variables according to the ordering. The second case in which directional consistency guarantees satisfiability if no domain is empty and no constraint is unsatisfiable is that of binary constraint problems whose graph has induced width 2, using strong directional path consistency. Indeed, this form of consistency guarantees that every assignment to a variable or a pair of variables can be extended to a higher variable, and width 2 guarantees that this variable is not joined to another pair of lower variables. The reason why the induced width is considered instead of the width is that enforcing directional path consistency may add constraints. Indeed, if two variables are not in the same constraint but are in a constraint with a higher variable, some pairs of their values may violate path consistency. Removing such pairs creates a new constraint. As a result, constraint propagation may produce a problem whose graph has more edges than the original one. However, all these edges are necessarily in the induced graph, as they are all between two parents