Maximal Tractable Fragments of the Region Connection Calculus: A Complete Analysis

1 Introduction

In qualitative spatial and temporal reasoning, knowledge is often represented by specifying the relationships be­ tween spatial or temporal entities. Of particular interest are disjunctions over a set of jointly exhaustive and pair­ wise disjoint (JEPD) relations. JEPD relations are also called base relations. Since any two entities are related by exactly one of the base relations, they can be used to represent definite information with respect to the given level of granularity. Indefinite information can be speci­ fied by disjunctions of possible base relations.

An important reasoning problem is deciding consis­ tency of a set of constraints using these relations, which is in many cases NP-hard. Sometimes deciding consis­ tency is tractable if only a subset of all possible dis­ junctions is used. If this subset contains all base rela­ tions, then instances of the NP-hard consistency prob­ lem can be solved by backtracking over tractable sub­ instances [Ladkin and Reinefeld , 1992; Nebel, 1997].

Larger tractable subsets often lead to more efficient solu­ tions (cf. [Renz and Nebel, 1998]). The goal is to identify the boundary between tractable and NP-hard subsets, i.e., all maximal tractable subsets containing all base re­ lations.

Two examples of these types of relations are Allen's interval algebra [Allen, 1983] mainly used for temporal reasoning and their spatial counterpart, Randell , Cui , and Cohn's [1992] Region Connection Calculus RCC-8. In the former case, the only maximal tractable subset containing all base relations has been identified [Nebel and Biirckert, 1995], in the latter case, only one max­ imal tractable subset has been identified so far [Renz and Nebel , 1999]. It was previously unknown whether there are others containing all base relations. For both subsets path-consistency is sufficient for deciding consis­ tency. Tractability and sufficiency of path-consistency have been proven by reducing the consistency problem to a tractable propositional satisfiability problem which requires very detailed knowledge about the considered set of relations and complicated proofs.

We present a new method for proving tractability and showing sufficiency of path-consistency for this kind of problem which does not require detailed knowledge about the considered set of relations. Applying this method, we identify two large new maximal tractable subsets of RCC-8 and show that these subsets together with the already known maximal tractable subset are the only such sets for RCC-8 that contain all base relations. We consider only sets containing all base relations , since only these sets enable efficient backtracking algorithms.

The paper is structured as follows . In Section 2 we introduce RCC-8. In Section 3 we present the new method for proving tractability. In Section 4 we identify two large subsets of RCC-8 which are candi­ dates for maximal tractable subsets, and apply our new method in Section 5 to show that both sets are tractable. In Section 6 the new method is used for find­ ing a consistent scenario. In Section 7 we apply the method to Allen's interval algebra after which we dis­ cuss and summarize our results. Some of our proofs are computer assisted. The programs are available at http://www.informatik.uni-freiburg.de/-sppraum.

2 The Region Connection Calculus RCC8

The Region Connection Calculus RCC-8 [Randell et al., 1992] is a language for qualitative spatial representation and reasor;ing where spatial regions are regular subsets of a topological space. Regions themselves do not have to be internally connected, i.e., a region may consist of different disconnected pieces.

RCC-8 contains eight JEPD base relations and all 2 8 possible disjunctions thereof. The base relations are denoted by DC, EC, PO, EQ, TPP, NTPP, TPP- 1 , and NTPP- 1 , with the meaning of DisConnected, Ex­ ternally Connected, Partial Overlap, EQual, Tangential Proper Part, Non- Tangential Proper Part, and their con­ verses. Two-dimensional examples of the base relations are shown in Figure 1. In the following we write sets of base relations to denote disjunctions of base relations. The disjunction of all base relations is called the univer­ sal relation. The subset of RCC-8 consisting of the eight base relations is denoted by B.

An important reasoning problem in this framework, denoted by RSAT, is deciding consistency of a set 8 of constraints of the form xRy, where R is an RCC-8 rela­ tion and x, yare spatial variables. The domain of spatial variables is the set of all spatial regions of the considered topological space. e is consistent if it has a solution, which is an assignment of spatial regions to the spatial variables of e in a way that all constraints are satis­ fied. When only relations of a specific subsetS s;; RCC-8 are used in 8, the corresponding reasoning problem is denoted by RSAT(S) . RSAT is NP-complete in general. Consistency of e can be approximated by using an 0 ( n 3 ) time path-consistency algorithm, which makes e path­ consistent by eliminating all the impossible labels (base relations) in every subset of constraints involving three variables [Mackworth, 1977]. If the empty relation oc­ curs during this process, then e is inconsistent, other­ wise the resulting set is path-consistent.

Renz and Nebel [1999] identified a tractable subset of RCC-8 (denoted by H8 ) containing all base relations which is maximal with respect to tractability, i.e., if any other RCC-8 relation is added to H8 , the consistency problem becomes NP-complete. They further showed that enforcing path-consistency is sufficient for deciding RSAT(H8 ). ii.8 contains 148 relations, i.e., about 60% of all RCC-8 relations.

3 A New Method for Proving Tractability of Sets of Relations

In this section we develop a new method for proving trac­ tability of reasoning over disjunctions of a JEPD set of binary relations over a domain D. Let A be a finite set of JEPD binary relations. We assume in the following that there is a relation I d E A such that I d( d, d) is satisfied for all d E D. I d is called identity relation. The consistency problem CSPSAT(S) for sets S s;; 2A over a domain Dis defined as follows [Renz and Nebel, 1999]:

Instance: A set V of variables over a domain D and a finite set 8 of binary constraints xRy, where R E S and x,y E V.

Question: Is there an instantiation of all variables in 8 such that all constraints are satisfied?

S denotes the closure of S under composition ( o), inter­ section (n) and converse('-"). CSPSAT(S) can be poly­ nomially reduced to CSPSAT(S) if the universal relation is contained inS [Renz and Nebel, 1999]. Therefore, we consider in the following only sets S s;; 2A with S = S.

Before we present our new method for showing that CSPSAT(S) is tractable for a set S, we define some ter­ minology. A refinement of a constraint xRy is a con­ straint xR' y such that R' s;; R. For instance, the con­ straint x{DC, TPP}y is a refinement of the constraint x{DC, EC, PO, TPP}y. A refinement of a set of con­ straints e is a set of constraints 8' that contains a re­ finement of every constraint of e. Every solution of 8' is also a solution of 8. A consistent scenario 8 8 of 8 is a refinement of 8 such that 8 8 is consistent and con­ tains only constraints over relations of A. We assume that a set of constraints 8 contains n ordered variables x1 , ... , Xn. The following definition will be central for our new method.

Definition 1 (reduction by refinement)

LetS, T s;; 2A. S can be reduced by refinement to T, if the following two conditions are satisfied:

1. for every relation S E S there is a relation Ts E T with Ts s;; S,
2. every path-consistent set 8 of constraints over S can be refined to a set 8' by replacing xiSXj E 8 with xiTSXj E 8' for i < j, 1 such that enforcing path-consistency to 8' does not result in an incon­ sistency.

Lemma 2 If path-consistency decides CSPSAT(T) for a set T s;; 2A, and S can be reduced by refinement to T, then path-consistency decides CSPSAT(S) .

Proof. Let 8 be a path-consistent set of constraints over S. Since S can be reduced by refinement to T, there is by definition a set 0' of constraints over T which is a refinement of 0 such that enforcing path-consistency to 0' does not result in an inconsistency. Path-consistency decides CSPSAT(T) , so 0' is consistent, and, hence, 0 is also consistent. ·

1 Note that we only refine constraints x;Sxj for i < j. This is no restriction, as by enforcing path-consistency the converse constraint x j S~ x; will also be refined. Rather it offers the possibility of refining, e.g., converse relations to other than converse sub-relations, i.e., if, for instance, R is refined to r, we can refine R ~ to a relation other than r ~ .

Since path-consistency can be enforced in cubic time, it is sufficient for proving tractability of CSPSAT(S) to show that S can be reduced by refinement to a set T for which path-consistency decides CSPSAT(T). Note that for refining a constraint xSy (S E S) to a constraint xTsy (Ts E T), it is not required that Ts is also con­ tained in S. Thus, with respect to common relations, the two sets S and Tare independent of each other.

We will now develop a method for showing that a set of relations S ~ 2A can be reduced by refinement to another set T ~ 2A. In order to manage the different refinements, we introduce a refinement matrix that con­ tains for every relation S E S all specified refinements.

Definition 3 (refinement matrix) A refinement matrix M of S has lSI x 2IAI Boolean entries such that for S E S , R E 2A, M[SJ[R] =true only if R ~ S.

For example, if the relation {DC, EC, PO, TPP} is al­ lowed to be refined only to the relations {DC, TPP} and {DC} , then M[{DC, EC, PO, TPP}][R] is true only for R = {DC, TPP} and for R = {DC} and false for all other relations R E 2A. M is called the basic refinement matrix if M[SJ[R] =true if and only if S = R.

We propose the algorithm CHECK-REFINEMENTS (see Figure 2) which takes as input a set of relations Sand a refinement matrix M of S. This algorithm computes all possible path-consistent triples of relations R12, R23 , R13 of S (step 4) and enforces path-consistency (using a standard procedure PATH-CONSISTENCY) to every re­ finement R~ 2 , R23 , R~ 3 for which M[Rij][R;j] = true for all i,j E {1,2,3},i < j (steps 5,6). If one of these refinements results in the empty relation, the al­ gorithm returns fail (step 7) . Otherwise, the result­ ing relations R~'2 , R~3 , R~3 are added to M by setting M[Rij][R;j] =true for all i,j E {1, 2, 3} , i < j (step 8). This is repeated until M has reached a fixed point (step 9), i.e., enforcing path-consistency on any possible re­ finement does not result in new relations anymore. If no inconsistency is detected in this process, the algorithm returns succeed.

A similar algorithm, GET-REFINEMENTS, returns the revised refinement matrix if CHECK-REFINEMENTS returns succeed and the basic refinement matrix if CHECK-REFINEMENTS returns fail. Since A is a finite set of relations, M can be changed only a finite number of times, so both algorithms always terminate.

Lemma 4 Let 0 be a path-consistent set of constraints over S and M a refinement matrix of S. For ev­ ery refinement 0' of 0 with XiR 1 Xj E 0' only if xiRXj E 0, i < j, and M[RJ[R'] = true: if CHECK­ REFINEMENTS(S, M) returns succeed, enforcing path­ consistency to 0' does not result in an inconsistency.

Algorithm: CHECK-REFINEMENTS Input: A setS and a refinement matrix M of S. Output: fail if the refinements specified in M can make a path-consistent triple of constraints over S inconsistent; succeed otherwise. 1. changes +- true 2. while changes do 3. oldM +- M 4. for every path-consistent triple T = (R12, R23, R13) of relations overS do 5. for every refinement T' = (R~ 2 , R;3, R~ 3 ) ofT with oldM[R1 2][R~2 ] = oldM[R23][R;3 ] = oldM[R1 3][R~ 3 ] = true do 6. T" +- PATH-CONSISTENCY(T') 7. ifT" = (R~'2 ,R~3 ,R~3 ) contains the empty relation then return fail 8. else do M[R12][R~2 ] +- true , M[R23][R~3 ] +- true, M[R13][R~'3 ] +- true 9. if M = oldM then changes +- false 10. return succeed Figure 2: Algorithm CHECK-REFINEMENTS

Proof. Suppose that CHECK-REFINEMENTS(S, M) re­ turns succeed and GET-REFINEMENTS(S, M) returns the refinement matrix M'. Suppose further that enforc­ ing path-consistency to 0' results in an inconsistency which is detected first for the three variables Xa,Xb,Xc· Suppose that for every pair of variables Xi, x j, xiRij x j E 0 and XiR;jxj E 0'. Enforcing path-consistency to 0' can be done by successively enforcing path-consistency to every triple of variables of 0'. Suppose that we start with the triple x1, x2, x3 . We have that M'[R;j][R;j] = true for every i,j E {1,2,3} ,i < j . After enforc­ ing path-consistency to this triple we obtain the rela­ tions R;j for which again M'[Rij][R;j] = true, other­ wise CHECK-REFINEMENTS(S, M) would have returned fail. The same holds when we proceed with enforcing path-consistency to every triple of variables, we always end up with relations Ri· for which M'[Rij][Rij] =true. Therefore, for all possible relations R~b ,Rbc,R~c we can obtain by enforcing path-consistency to 0' we have that M'[Rij][Ri-] =true for all i,j E {a,b,c},i < j. If this triple oF relations were inconsistent , CHECK­ REFINEMENTS(S, M) would have returned fail. ·

If CHECK-REFINEMENTS returns succeed and GET­ REFINEMENTS returns M', we have pre-computed all possible refinements of every path-consistent triple of variables as given in the refinement matrix M'. Thus, applying these refinements to a path-consistent set of constraints can never result in an inconsistency when enforcing path-consistency.

Theorem 5 Let S , T ~ 2A, and let M be a refinement matrix of S. GET-REFINEMENTS(S, M) returns the re­ finement matrix M'. If for every S E S there is a Ts E T with M'[S][Ts] =true, then S can be reduced by refine­ ment toT.

Proof. By the given conditions, we can refine every path-consistent set 0 of constraints over S to a set 0' of constraints overT such that M'[Ri1 ][R~ 1 ] = true for every XiRijXj E 0 and XiR~ 1 x1 E 0', i < j, R~j E T. M' is a fixed point with respect to GET-REFINEMENTS, i.e., GET-REFINEMENTS(S, M') returns M', thus it fol­ lows from Lemma 4 that enforcing path-consistency to 0' does not result in an inconsistency. ·

By Lemma 2 and Theorem 5 we have that the procedures CHECK-REFINEMENTS and GET-REFINEMENTS can be used to prove tractability for sets of relations.

Corollary 6 Let S , T ~ 2A be two sets such that path­ consistency decides CSPSAT(T), and let M be a re­ finement matrix of S. GET-REFINEMENTS(S, M) re­ turns M'. If for every S E S there is a Ts E T with M'[S][Ts] = true, then path-consistency decides CSPSAT(S).

In the following sections we apply this method to the Region Connection Calculus RCC-8 and to Allen's inter­ val algebra for proving certain subsets to be tractable. For RCC-8 it will help us make a complete analysis of tractability by identifying two large new maximal tractable subsets. Later, it will turn out that the new method can be used for identifying the fastest possible algorithms for finding a consistent scenario.

4 Candidates for Maximal Tractable Subsets of RCC8

In order to identify maximal tractable subsets of a set of relations with an NP-hard consistency problem, two dif­ ferent tasks have to be done. On the one hand, tractable subsets have to be identified. On the other hand, NP­ hard subsets have to be identified. Then, a tractable subset is maximal tractable if any superset is NP-hard. If tractability has not yet been shown for certain subsets, the NP-hardness results restrict the number of different subsets that still have to be analyzed for tractability.

In this section we present new NP-hardness results for RCC-8 and identify those subsets that are candidates for maximal tractable subsets, i.e., if any other relation is added to one of those candidates they become NP-hard. Before this, we summarize Renz and Nebel's [1999] NP­ hardness proofs that were necessary for showing that ii.8 is a maximal tractable subset of RCC-8.

Lemma 7 (Renz and Nebel, 1999) RSAT(B U {R}) is NP-hard if R EN~ RCC-8, where:

Renz and Nebel [1999] proved maximality of ii.8 by showing that RSAT(ii.8 U {EQ, NTPP}) is NP-hard and that the closure of ii.8 plus any relation of RCC-8 \ (ii.8 U N) contains the relation {EQ, NTPP}. This NP-hardn~ss proof, however, does not make use of all relations of W-8 , but only of the relations {EC, TPP} and {EC, NTPP} .

Thus, any set of RCC-8 relations that contains all base relations plus the relations {EC, TPP} , {EC, NTPP} , and {EQ, NTPP} is NP-hard.

This result rules out a lot of subsets of RCC-8 to be tractable, but still leaves the problem of tractability open for a large number of subsets. We found, however, that it is not necessary that both relations, {EC, TPP} and {EC, NTPP} , must be added to {EQ, NTPP} in order to enforce N P-hardness. It is rather sufficient for N P­ hardness that only one of them is added to {EQ, NTPP} .

This is shown in the following two lemmata. They are proven by reducing 3SAT, the NP-hard satisfiability problem of propositional formulas that contain exactly three literals per clause [Garey and Johnson, 1979], to the respective consistency problem. Both reductions are similar to the reductions given in [Renz and Nebel, 1999]: every literal as well as every literal occurrence L is re­ duced to a constraint XLRY L where R = Rt U Rt and Rt n Rt = 0. L is true iff XLRtY L holds and false iff X LRt Y L holds. "Polarity constraints" enforce that X~LRtY ~L holds iff XLRtY L holds, and vice versa. "Clause constraints" enforce that at least one literal of every clause is true.

Lemma 8 If (B U { {EQ, NTPP}, {EC, NTPP}}) ~ S, then RSAT(S) is NP-complete.

Proof Sketch. Transformation of 3SAT to RSAT(S). Rt = {NTPP} and Rt = {EQ} . Polarity constraints:

Clause constraints for each clause c = { i, j, k}: Yi{NTPP- 1 }Xj, Y1{NTPP- 1 }Xk , Y k{NTPP- 1 }Xi· {DC, EC} is contained in S. ·

Lemma 9 If (BU{ {EQ, NTPP} , {EC, TPP}}) ~ S, then RSAT(S) is NP- complete.

Proof Sketch. Transformation of 3SAT to RSAT(S). Rt = {NTPP} and Rt = {EQ}. Polarity constraints:

Clause constraints for . each clause c = { i, j, k }: Yi{NTPP- 1 }Xj, Yi{NTPP- 1 }Xk, Y k{NTPP- 1 }Xi. All the above relations are contained in S. ·

Using these results, four other relations can be ruled out to be contained in any tractable subset of RCC-8, since the closure of the base relations plus one of the four relations contains {EQ, NTPP} as well as {EC, TPP}.

Definition 10 The two sets NP8 and P8 are defined as follows:

• NP8 = N u { {EC, NTPP, EQ} , {EC, NTPP- 1 , EQ} , {DC, EC, NTPP, EQ} , {DC, EC, NTPP- 1 , EQ} }.
• Ps = RCC-8 \NPs.

NP8 contains 76 relations, P8 contains 180 relations. Corollary 11 RSAT(BU{R}) is NP -hard, if R E NPs.

Lemmata 8 and 9 give us a sufficient but not neces­ sary condition of whether a subset of P8 is NP-hard, namely, if B ~ S ~ P8 contains {EQ, NTPP} and one of {EC, TPP} or {EC, NTPP}, RSAT(S) is NP-hard, other­ wise the complexity of RSAT(S) remains open.

We computed all subsets of P8 that are candidates for maximal tractable subsets with respect to the above two NP-hardness p:._oofs, i.e., we enumerated all subsets S ~ P8 with S = S that contain all base relations and the universal relation, and checked whether they fulfilled the following two properties:

1. S does not contain ( {EQ, NTPP} and {EC, TPP}) or ( {EQ, NTPP} and {EC, NTPP} ), and
2. the closure of S plus any relation of P8 \ S contains ( {EQ, NTPP} and {EC, TPP}) or ( {EQ, NTPP} and {EC, NTPP} ).

To our surprise, this r~sulted in only three different sub­ sets of P8 , of which tis is of course one of them. The other two subsets are denoted by Cs and Qs. 2

Cs contains 158 different RCC-8 relations, Qs contains 160 different relations. We have that Hs U Cs = P8 .

Lemma 12 For every subsetS of RCC-8: If RSAT(S) is tractable, then S ~ Hs, S ~ Cs, or S ~ Qs .

Proof. By computing the closure of every set contain­ ing the base relations, the universal relation, and two arbitrary RCC-8 relations, the resulting set is either contained in one of the sets Hs, Cs, or Qs, or is NP-hard according to Lemma 8, Lemma 9, or Corollary 11. ·

So far we did not say anything about tractability of Cs or Qs or subsets thereof. It might be that both sets are NP-hard or that there is a large number of different maximal tractable subsets that are contained in the two sets. What we obtained so far is, thus, only a restriction of the number of different subsets we have to check for tractability. However, we will see in the next section that both Cs and Qs are in fact tractable.

5 A Complete Analysis of Tractability

In [Renz and Nebel, 1999] tractability of Hs was shown by reducing ~SAT(Hs) to HORNSAT. This was possi­ ble because tis contains exactly those relations that are transformed to propositional Horn formulas when using the propositional en~oding of RCC-8. This propositional Horn encoding of tis was also used for proving that path-consistency decides RSAT(H8 ) [Renz and Nebel , 1999], by relating positive unit resolution, which is a complete decision method for propositional Horn formu­ las, to path-consistency. The propositional encoding of Cs and Qs is neither a Horn formula nor a Krom formula (two literals per clause), so it is not immediately possible to reduce the consistency problem of these subsets to a tractable propositional satisfiability problem. Therefore we have to find other ways of proving tractability.

2 The names were chosen, since all Ps-relations not con­ tained in Cs contain E~, and all Ps-relations not contained in Qs contain EQ..

Let us have a closer look at the relations of the two sets Cs and Q8 and how they differ from H8 .

Proposition 13 For all relations R E Ps \ Hs we have that {EQ} C R. For all refinements R' of R with R' U {EQ} = R and {EQ} Cl R' we have that R' E ii.s .

Cs and Qs are both subsets of Ps, so if we can prove the following conjecture, then both sets are tractable:

Conjecture 14 Let 0 be a path-consistent set of con­ straints over Cs or over Q8 . If 0' is obtained from 0 by eliminating the identity relation { EQ} from every constraint xRy E 0 with R E Ps \ Hs, then enforcing path­ consistency to 0' does not result in an inconsistency.

If we can prove this conjecture, then, by Proposition 13, 0' contains only constraints over Hs. Since path­ consistency decides RSAT(H8 ), we then have that if 0 is path-consistent, 0' is consistent and, therefore, 0 is also consistent , i.e., path-consistency decides consistency for sets of constraints over Cs and over Qs. In [Gerevini and Renz, 1998] it was shown that the relation {EQ} can always be eliminated from every constraint of a path­ consistent set of constraints over H8 without changing consistency of the set. This was, again, shown by ap­ plying positi::_e unit resolution to the propositional Horn encoding of tis, a method which is not applicable in our case. Instead, we can now apply the new method devel­ oped in Section 3, namely, we can check whether Cs and Qs can be reduced by refinement to ii.s. Conjecture 14 gives the refinement matrix we have to check. We define this particular refinement matrix for arbitrary sets S of disjunctions over a set A of JEPD relations:

Definition 15 (identity-refinement matrix) M# is the identity-refinement matrix of a set S ~ 2A if for every S E S, M"'[S][S'] = true iff S' = S \ Id, where I d E A is the identity relation.

Proposition 16

• CHECK-REFINEMENTS(Cs, M#) returns succeed.
• CHECK-REFINEMENTS(Qs, M#) returns succeed.

Theorem 17 Path-consistency decides RSAT(Cs) as well as RSAT(Qs).

Proof. It follows from Proposition 13 and Proposi­ tion 16 that Theorem 5 can be applied with T = Hs. Since path-consistency decides RSAT(Hs), it follows from Corollary 6 that path-consistency decides RSAT(C8 ) as well as RSAT(Q8 ) ·

Together with Lemma 12 it follows that H8 , C8 , and Q8 are the only maximal tractable subsets of RCC-8 that contain all base relations.

Theorem 18 For every subsetS of RCC-8 that contains all base relations and the universal relation: RSAT(S) is tractable iff S ~ H8 , S ~ Cs , or S ~ Qg .

6 Finding a Consistent Scenario

Gerevini and Renz [1998] gave an O(n 3 ) time algorithm for computin~ a consistent scenario for a set of con­ straints over 1-ls. Their algorithm is based on first elimi­ nating {EQ} from every constraint and then successively refining constraints to constraints over base relations in a particular order and enforcing path-consistency in be­ tween. As shown in the previous section it is also pos­ sible to eliminate {EQ} from all constraints over C8 and over Q8 , so it is possible to apply Gerevini and Renz's algorithm also for C8 and Q8 . By applying the method developed in Section 3 we can, however , improve this al­ gorithm for all three maximal tractable subsets of RCC-8.

Lemma 19 Hs, Cs, and Qs can be reduced by refine­ ment to B, the set of all RCC-8 base relations.

This gives us the possibility of computing a consistent scenario of a path-consistent set of constraintf) over a tractable subset by a simple table lookup scheme, which is the fastest possible way.

Lemma 20 LetS be one of H8 , C8 , Q8 . For every re­ lation R E S , base(R) is the following base relation:

• (1} If REB, then base(R) = R ;
• else if {DC} ~ R, then base(R) ={DC};
• else if {EC} ~ R and S = Qg or S = Hs, then base(R) = {EC};
• else if {PO}~ R , then base(R) ={PO} ;
• else if {NTPP} ~ R and S = C8 , then base(R) = {NTPP};
• (6} else if {TPP} ~ R, then base(R) = {TPP} ;
• else base(R) = base(R'---').

Theorem 21 A consistent scenario e. of a path­ consistent set e of constraints over H8 , C8 , or over Q8 can be computed in O(n 2 ) time, by replacing every con­ straint xRy E e with xR'y E e., where R' = base(R).

7 Applying the New Method to Allen's Interval Algebra

The method developed in Section 3 can also be applied to Allen's interval algebra [Allen, 1983] which consists of the 13 JEPD relations before ( <), meets (m) , overlaps ( o), starts ( s), during (d), finishes (f), their converse re­ lations> , mi , oi, si, di, fi, and the identity relation equal ( =) that describe the possible relationships between two convex intervals. The full algebra consists of the 2 13 pos­ sible disjunctions of the base relations and has an NP­ complete consistency problem. Tractable subclasses of the interval algebra for which path-consistency decides consistency were identified by Vilain et a!. [1989], the "Pointisable" subclass P (about 2% of the full algebra), and by Nebel and Biirckert [1995], the "ORD-Horn" sub­ class 1-l (about 10% of the full algebra) which is the only maximal tractable subclass of the interval algebra that contains all base relations.

Since the only maximal tractable subclass of the inter­ val algebra containing all base relations has already been identified, we cannot provide any new results on that topic. We can, however, validate the usefulness of our new method by showing that tractability of the ORD­ Horn subclass and sufficiency of path-consistency for de­ ciding consistency for this subclass can also be proven using our method. For this we apply the same strategy as for C8 and Q8 , namely, we use the identity-refinement matrix M-:f. (cf. [Ligozat, 1996]) .

Proposition 22 GET-REFINEMENTS(}{ , M-:f.) returns MP which has the following property: For every R E 1-l there is an R' E P such that MP [ R] [ R'] = true .

This was computed in less than 25 minutes on a Sun Spare Ultral. We can now apply Theorem 5:

Theorem 23 1-l can be reduced by refinement to P .

Not all of the 188 pointisable relations are necessary for this refinement, but only 30 of them which are obtained according to the following refinement scheme.

Lemma 24 For every relation R E 1-l , point(R) is the following pointisable relation where R-:f. = R \ { =} and R' = Rn {<,>,o,oi, d,di }:

1. If R ={=} , then po'int(R) = R;
2. (2} else if R' =I={}, then point(R) = R';
3. else point(R) = R -:f..

Using this refinement scheme, every path-consistent set e of constraints over ORD-Horn can be refined to a path­ consistent set e' by replacing every constraint xRy E e with xR'y E e', where R' = point(R). This can be useful for some tasks such as finding a consistent scenario (cf. [Gerevini and Cristani , 1997]).

8 Discussion & Further Work

The method we developed for proving tractability of rea­ soning over sets of relations is very simple, does not re­ quire detailed knowledge about the considered relations, and seems to be very powerful. The only difficulty of this method is finding an adequate refinement matrix. However, the simple heuristic of eliminating all iden­ tity relations was successful for all maximal tractable fragments of RCC-8 and Allen's interval algebra which contain all base relations . This leads to an interesting question, namely, whether it is a general property of sets of relations containing all base relations for which path­ consistency decides consistency that the identity rela­ tion can be eliminated from all constraints of a path­ consistent set without making the set inconsistent.

The complete analysis of tractability for RCC-8 gives the possibility to develop more efficient algorithms for deciding consistency. As Renz and Nebel [1998] have shown in an empirical study, running different strategies in parallel is very effective; almost all apparently hard in­ stances of the phase-transition region up to a certain size were solved in a few seconds. The two maximal tractable subsets of RCC-8 identified in this paper suggest several new strategies that should be empirically studied. Both subsets are larger than H8 , but their average branching factor is higher (C8 : 1.523, Qg: 1.516, Hs: 1.438).

9 Summary

We developed a general method for proving sufficiency of path-consistency for deciding consistency of disjunctions over a set of JEPD relations. We applied this method to the Region Connection Calculus RCC-8 and identified two large new maximal tractable subsets. Together with H8 , the already known maximal tractable subset, these are the only such sets for RCC-8 that contain all base relations and can, hence, be used to increase efficiency of backtracking algorithms for reasoning over NP-hard subsets. We also applied our method to Allen's interval algebra which resulted in a simple proof of tractability of reasoning in the ORD-Horn subclass.

Acknowledgments

This research was supported by DFG as part of the project FAST-QUAL-SPACE, which is part of the DFG special research effort on "Spatial Cognition". I want to thank Christoph Dornheim and Bernhard Nebel for their helpful comments.