

![0_image_0.png](0_image_0.png)

transition is around d = 8 to d = 10 depending on the instance size (see Figure 5). Because of the result of our theoretical analysis of the occurrence of trivial flaws (see Section 3), it can be expected that for larger instance sizes the phase-transition behavior will be overlaid and mainly determined by the expected number of locally inconsistent triples which also depends on the average degree d . Thus, although it seems that the phase-transition shifts towards larger values of d as the instance size increases, the phase-transition is asymptotically below d = 9.44, the theoretical value for n -> <> (see Section 3). Instances which are not pathconsistent can be solved very fast by just one application of the path-consistency algorithm without further need for backtracking. When looking at the median CPU times given in Figure 5, one notices that there is a sharp decline of the median CPU times at the phase transition. This indicates that for values of the average degree which are higher than where the phase-transition occurs, at least 50% of the instances are not path-consistent.

When using only "hard" relations, i.e., relations in NP 8 , the phase-transition appears at higher values for d, namely, between d = 10 and d = 15 (see Figure 6). As the median runtime shows, these instances are much harder in the phase-transition than in the former case. As in the previous case, but even more strongly, it seems that the phase-transition shifts towards larger values of d as the instance size increases, and also that the phasetransition region narrows.

In order to evaluate the quality of the path-consistency method as an approximation to consistency, we counted the number of instances that are inconsistent but path-consistent
(see Figure 7), i.e., those instances where the approximation of the path-consistency algorithm to consistency is wrong. First of all, one notes that all such instances are close to the phase transition region. In the general case, i.e., when constraints over all RCC-8 relations are employed, only a very low percentage of instances are path-consistent but inconsistent.

Therefore, the figure looks very erratic. More data points would be required in order to obtain a smooth curve. However, a few important observations can be made from this figure, namely, that path-consistency gives an excellent approximation to consistency even for instances of a large size. Except for very few instances in the phase-transition region, almost all instances which are path-consistent are also consistent. This picture changes