

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

whi h have to be he ked by the algorithm. The pathonsisten y omputation during the ba ktra king sear h is dierent, however. There, only the paths involving the urrently hanged onstraint are entered in the queue, sin e only these paths might result in hanges of the onstraint graph. This is mu h faster than the full omputation of pathonsisten y whi h is only done on e at the beginning of the ba ktra k sear h.

## 5. The Phase-Transition Of Rcc-8

When randomly generating problem instan es there is usually a problem-dependent parameter whi h determines the solubility of the instan es. In one parameter range instan es are under onstrained and are therefore soluble with a very high probability. In another range, problems are over onstrained and soluble with a very low probability. In between these ranges is the phase-transition region where the probability of solubility hanges abruptly from very high to very low values (Cheeseman et al., 1991). In order to study the quality of dierent heuristi s and algorithms with randomly generated instan es of an NP-
omplete problem, it is very important to be aware of the phase-transition behavior of the problem.

This is be ause instan es whi h are not ontained in the phase-transition region are often very easily solvable by most algorithms and heuristi s and are, thus, not very useful for omparing their quality. Conversely, hard instan es whi h are better suited for omparing the quality of algorithms and heuristi s are usually found in the phase-transition region.

In this se tion we identify the phase-transition region of randomly generated instan es of the RSAT problem, both for instan es using all RCC-8 relations and for instan es using only relations of N P8. Similarly to the empiri
al analysis of qualitative temporal reasoning problems (Nebel, 1997), it turns out that the phase-transition depends most strongly on the average degree d of the nodes in the onstraint graph. If all relations are allowed, the phase-