explicitly c is the number of cliques in the constraint graph and g is the maximum degree of a node in the constraint graph   The neighborhood of i is the set of variables adjacent to i in the constraint graph  A domain D'    { D', D', . . . } is a sub-domain of D
{Di, Di, . . .}
if Vi, D! C Di An instantiation I of a set of variables S is a set of value assignments
{Ij}jES one for each variable belonging to S s t  Vj E Sj   Ij E Dj An instantiation I of S satisfies a constraint C ij if { ij } Q S or C ij Ij, Ij is true An instantiation is consistent if it satisfies all the constraints A pair of values i, a , j, b is path consistent if for all k E X s t  j / k / i / j  this pair of values can be extended to a consistent instantiation of {i, j, k} j, b is a path consistent support for i, a if  a, b  E Ci, and   i, a , j, b  is path consistent A solution of P X, D, C is a consistent instantiation of X A value i, a  is consistent if there is a solution I such that I i    a  and a CN is consistent if it has at least one solution  We denote by P | D i ={ a } the CN obtained by restricting D i to { a } in P If LC is a local consistency a CN P is not LC consistent iff LC does not hold on P
A CN P is LC inconsistent iff we cannot obtain a LC consistent constraint network by deletion of some local inconsistencies in P If a local consistency LC is used to detect the inconsistency of instantiations no longer than   we can say that a CN P
X, D, C is LC inconsistent iff there is no sub domain D ′ of D such that LC holds on  X, D ′ , C

## 3. The Local Consistencies Studied

Filtering techniques can be used to detect the inconsistency of a CN and under some assumptions they can ensure a backtrack free search Freuder However their usual purpose is not to find a solution in a constraint network  They remove some local inconsistencies and so delete some regions of the search space that do not contain any solution The resulting CN is equivalent to the initial one since the set of solutions is unchanged but if substantial reductions are made the search becomes easier In this section we review the basis of arc consistency k consistency restricted path consistency and inverse consistencies  Furthermore  we extend the idea of restricted  path consistency to k restricted path consistency and Max restricted path consistency  We propose a new class of local consistencies called singleton consistencies We also show a property of path inverse consistency that can be used to have an optimal worst case time complexity in a path inverse consistency algorithm  Debruyne Arc consistency The most widely used local consistency is arc consistency It is based on the notion of support A value is viable as long as it has at least one compatible value in the domain of each neighboring variable  An AC algorithm has to remove the values that have no support on a constraint As in most of the filtering techniques  the value deletions have to be propagated through the network since they can lead to the arc inconsistency of some values that were previously viable k-consistency  A consistent instantiation of length k  is k consistent  ie k consistent in the formalism of Freuder if it can be extended to any additional k th variable The time and space complexities of enforcing k consistency are polynomial with the exponent dependent on k   If k >    the constraints have to be represented in extension to store the k tuples deleted and the structure of the network can be changed This leads to huge space requirements and subsequently important cpu time costs In practice