

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

each. In Figure 13 we give the average number of visited nodes of the path-consistent instances. It can be seen that for our test instances the average number of visited nodes is linear in the size of the instances. The percentile 70% CPU time for instances of the phase-transition with a size of n = 500 regions is about 20 seconds, the percentile 99% CPU
time is about 90 seconds. Up to a size of n = 400 regions, the percentile 99% CPU time is less than a minute (see Figure 14).

131,240 of our test instances were already solved by the H s / static/ global heuristic, for 71 instances the Hs/dynamic/local heuristic was required and for 577 instances the C 8 /dynamic/local heuristic produced the solution. None of the 112 instances which were not solved by one of those three heuristics were solved by the B/static/local heuristic. We tried to solve these instances using the other heuristics, again using a maximal number of 2n visited nodes each. The best performing among those heuristics was the C 8 /dynamic/global heuristic which solved 87 of the 112 instances followed by the C 8 /static/global heuristic (83)
and the Q s /dynamic/global heuristic (63). 7 instances were not solved by any heuristic within a maximal number of 2 n visited nodes.

## 9. Discussion

We empirically studied the behavior of solving randomly generated RSAT instances using different backtracking heuristics some of which make use of the maximal tractable subsets identified in previous work. We generated instances according to two different models of which the "general model" A allows all 256 RCC-8 relations to be used while the "hard model" H allows only relations whi are not contained in any of the maximal tractable subsets. A theoretical analysis of the two models showed that the model H and the model A for a small average degree of the nodes in the constraint graph do not suffer from trivial local inconsistencies as it is the case for similar generation procedures for CSPs with finite domains (Achlioptas et al., 1997).  It turned out that randomly generated instances of both models show a phase-transition behavior whi depends most strongly on the average degree of the instances. While most instances outside the phase-transition region can be