This is especially obvious on Graph and Graph However it is difficult to say which is the most interesting local consistency on these problems since even if SAC and SRPC
and Graph that they can be far more pruningful are costly  we can see on Scen These problems highlight that NIC is not very stable. It sometimes shows good per formances but an exponential explosion can lead to a prohibitive cost on some instances When NIC requires a reasonable time its pruning efficiency is closer to the one of Max RPC  than to the one of SAC   These results confirm that if the neighborhoods of the variables are not small NIC can be really prohibitive On Graph PIC
and obviously the algorithms enforcing a stronger local consis tency finds the inconsistency of the problem whereas AC and RPC remove only a part tof the inconsistent values  We can see a similar behavior on Graph w here Max RPC
wipes out a domain whereas AC RPC and PIC do not find the inconsistency of the problem On these instances Max RPC is the best choice

## 6.2 Randomly Generated Problems

The random uniform CN generator of section is used to compare the cpu time required to enforce the local consistencies We have to point out that NIC has not been designed to be used on uniform CNs but to adapt filtering effort to the degree of the variables in the constraint graph  So  NIC would have better performances on non uniform CNs than that hose presented in this section  The generated problems have variables and val ues in each initial domain Figure shows the results on CNs with density of These CNs are relatively sparse since the variables have four neighbors on average  Figure presents performances at density the variables have neighbors on average   Because of the to set of parameters there are no flawed variables MacIntyre  Prosser  Smith Wals h in the generated problems ® In addition to the algorithms of the previous section  we use a strong path consistency algorithm based on PC   Chmeiss   Jégou and AC
This algorithm stops as soon as a domain wipe out occurs or as soon as a constraint no longer allows any pair of values In addition to the percentage of deleted values and cpu time performances  Figure   and Figure   show the cpu time to number of deleted values ratio for each tightness where the local consistency removes at least one value on average For each tightness instances were generated  Figure   and Figure   show mean values obtained on a Pentium II
Mhz with    Mb of memory under Linux II As observed in  Gent  MacIntyre  Prosser  Shaw Wals h for arc consistency the filtering algorithms tested have a complexity peak  For low values of the tightness  they easily prove that the values are locally consistent and when constraints are very tight they quickly wipe out a domain Each local consistency has a phase transition where most of the hardest problems for an algonthm achieving this local consistency tend to occur

## 6.3 Experiments On Sparse Cns

Even on sparse CNs  see Figure    the cpu time results are so different between the al gonthms h min for strong PC at its peak when AC requires at most sconds on average that a logarithmic scale has to be used Strong PC is really prohibitive even for 6. In Section 5.2,the tightness reaching 1, there was obviously flawed variables for some sets of parameters.