RCC8 Is Polynomial on Networks of Bounded Treewidth

1 RCC8

RCC8 is a spatial representation formalism derived from the region connection calculus [Randell et al., 1992b; Cohn and Hazarika, 2001], a multi-sorted first order theory based on a primitive binary relation, C, expressing connectedness of spatially extended entities (referred to as regions). Since different versions of the RCC theory can be found in the literature, we introduce RCC models in terms of specific Boolean contact algebras [Bennett and D¨untsch, 2007]. For the purposes of this paper, an RCC model is a model of the theory of non-trivial Boolean algebras (0 ̸=1) and the following axioms (where x ≤ y is defined as x · y = x): (a) ∀xy(C(x, y) ⇒ x,y̸=0), (b) ∀x(x ̸=0⇒C(x,x)), (c) ∀xy(C(x,y)⇒C(y,x)), (d) ∀xy(x ≤ y ⇔ ∀z(C(x, z) ⇒C(y, z))), (e) ∀xyz(C(x, y+z) ⇒ C(x, y) ∨C(x, z)), and (f) ∀x(x ̸=0, 1 ⇒C(x, -x)).

Examples of RCC models can be generated from regular, connected topological spaces when regular closed subsets are conceived of as regions and the contact relation holds between such sets if and only if they interesect. It should be mentioned that RCC models can even be characterized in a topological sense [Bennett and D¨untsch, 2007]: each RCC model is isomorphic to a substructure of the RCC model induced (via the standard interpretation) by some weakly regular and connected T1 space (here weakly regular refers to a pointless variant of the regularity separation axiom).

In terms of RCC models the RCC8 relations DC (disconnected), EC (externally connected), PO (partial overlap), EQ (equals), TPP (tangential proper part), and NTPP (nontangential proper part) (as well as the converse relations of TPP and NTPP) may be introduced as follows:

where P(x,y) is defined as x ̸=0 ∧ x ≤ y and PP(x,y) as P(x,y)∧y ̸≤x. Note that in RCC models as defined above the relation EQ entails the identity relation (they are strict models in the sense of [Stell, 2000]). From the definitions it follows that for each RCC model, the set of RCC8 relations induces a relational partition scheme on the set of its non-null regions.

Definition 1 (cp. [Ligozat and Renz, 2004]). A relational partition scheme on D is a finite set, B, of (possibly empty) binary relations on D that forms a partition of D×D, contains the diagonal (or identity) relation {(x,x) : x ∈D}, and is closed under converses (i.e., B-1 := {(y,x) : (x,y) ∈ B} ∈ B for B ∈ B). The elements of B are referred to as base relations, and unions of base relations are referred to as general relations of the partition scheme.

In general, the set of general relations is not closed under composition, i.e., for general relations R and S, the composition R ◦ S := {(x, z) ∈ D 2 : ∃y((x, y) ∈ R∧ (y, z) ∈ S)} need not be a general relation of the partition scheme. This is specifically the case for RCC8 partition schemes induced by RCC models (see, e.g., [Bennett and D¨untsch, 2007]).

To enable reasoning on the symbolic level (see section 2) when satisfiability of formulae needs to be checked with respect to a class of models, one identifies a composition function (usually recorded as a table) that provides the strongest upper approximation for the composition of concrete relations in all models of that class. The RCC8 composition function ◦RCC8 is defined in Table 1 (see e.g. [Randell et al., 1992a]). The entry in row R and column S shows the base relations T1, . . . ,Tk such that {T1, . . . ,Tk} = R◦RCC8 S. It can be shown that each RCC model satisfies the RCC8 composition table in the sense that it satisfies all formulae

where R and S are symbols in the relational signature of RCC8 base relations, τ, and R◦RCC8 S = {T1, . . . ,Tk}. If we write general relations R representing a union of base relations B1 ∪ · · · ∪Bm as sets {B1, . . . ,Bm}, then converse and composition of general relations can be defined as follows: R-1 :={B-1 : B∈R} and R◦RCC8 R′ := ⋃B∈R,B′ ∈R′ B◦RCC8 B′ . By these settings the set of general relations becomes a set algebra that is closed under this approximative composition.

Definition 2. Let τ be the relational signature of RCC8 relations. An RCC8 model is a τ-structure, A, with non-empty domain A such that (a) {EQ A,DC A, . . . ,NTPPi A} defines a relational partition scheme on A, (b) EQ A is the identity relation, (c) DC A , EC A and PO A are symmetric, (d) TPPi A is the converse of TPP A and NTPPi A the converse of NTPP A , and (e) when R ◦RCC8 S = {T1, . . . , Tk}, then A satisfies (∗).

An RCC8 model A is called extensional if composition in A coincides with the RCC8 composition table. Examples of RCC8 models include the closed disks model (regions are closed disks in the Euclidean plane) and the model by Egenhofer [1991] (regions are Jordan curve bounded regions of the Euclidean plane, i.e., regions that are homeomorphic to the unit disk). Both models are known to be extensional [Bennett and D¨untsch, 2007; Li and Ying, 2003].

2 Constraint-based Reasoning with RCC8

Given the relational signature of RCC8 relations, τ, we now introduce basic concepts of constraint-based reasoning with RCC8. An RCC8 constraint network is defined by a finite set of variables V and a finite set of constraints between pairs of variables. Each constraint specifies a general relation that needs to hold between these variables. Since the set of RCC8 relations is closed under intersections, we may cast a constraint network as a directed and simple labeled graph 〈V,E, l〉. Its arcs E are simply the scopes of the constraints in the network, and to each such arc, the labeling function l assigns the constraint relation R (i.e., some subset of the signature τ). A solution of a constraint network 〈V,E, l〉 with respect to an RCC8 model A with domain A is a function ∗I : V →A such that for each arc (v1,v2) in E, (v I 1 ,v I 2 ) ∈ R A for some R ∈ l(x, y). A constraint network is said to be satisfiable in A if it has a solution in A and it is said to be satisfiable if it has a solution in some RCC8 model.

.

The network consistency problem for RCC8 is the following computational problem: given as input an RCC8 constraint network, decide whether the network is satisfiable in some RCC8 model. This problem is NP-complete in general (see, e.g., [Renz and Nebel, 2007]). The network consistency problem is the central problem for reasoning with RCC8, since many other reasoning tasks, such as entailment checking, can be reduced to it.

A constraint network 〈V,E, l〉 is called atomic if for each (x,y) ∈ E, l(x,y) is a singleton set, complete if E =V ×V, and normalized if it is complete and it holds l(x,x) = {EQ} as well as l(x, y) = l(y, x)-1 . A constraint network 〈V ′ ,E ′ , l ′ 〉 is called a refinement of 〈V,E, l〉 if V = V ′ , E ⊆ E ′ , and l ′ (x,y) ⊆ l(x,y) for each arc (x,y) ∈ E, and called a subnetwork if V ′ ⊆ V, E ′ ⊆ E, and l(x,y) ⊆ l ′ (x,y) for each arc (x, y) ∈ E ′ . A normalized RCC8 constraint network 〈V,E, l〉 is said to be path-consistent if l(x, y) ⊆ l(x, z) ◦RCC8 l(z, y) for each triple of variables x, y, z in V . Note that each RCC8 constraint network can be transformed into an equivalent normalized network. Moreover, each constraint network can be refined into an equivalent path-consistent constraint network. This can be achieved if each of the labels l(x,y) is refined by applying the operation

where z is any third variable occurring in the network, until a fixpoint is reached. For implementation details of this pathconsistency procedure see, for example, [Mackworth, 1977; Renz and Nebel, 2007]). If the resulting constraint network has empty labels, the original network is unsatisfiable.

3 Homomorphisms, Embeddings, Amalgamation

In the proof of our tractability result we use a result from [Bodirsky and Dalmau, 2008], which is formulated in a slightly different formalism, namely the homomorphism formulation of constraint satisfaction problems. Let A be a relational structure with a finite relational signature τ. Then the constraint satisfaction problem of B, CSP(B), is the computational problem to decide for a finite τ-structure A whether A homomorphically maps to B. A homomorphism from A to B is a map f : A→B such that for all a,b ∈ A and each binary R ∈ τ with aR A b, it holds f (a)R B f (b); for higherary relations, the definition is analogous, but not needed here. We will see later that the network consistency problem for RCC8 can be viewed as a constraint satisfaction problem for a certain infinite structure S; more importantly, we show that S has certain pleasant model-theoretic properties that allow us to derive our tractability result. We make the convention that the domains of structures A,B,C, . . . will be denoted by A,B,C, . . . , respectively. For a subset S of the domain A of A, we write A[S] for the substructure of A induced by S. In this paper, substructure always means induced substructure, as in [Hodges, 1997]. An embedding of a τ-structure A in a τ-structure B is a mapping f : A→B that is an isomorphism between A and B[ f (A)]. The age of a relational structure A is the set of finite structures that embed into A. A class of finite structures C with relational signature τ is an amalgamation class if C is nonempty, closed under isomorphisms and taking substructures, and has the amalgamation property, which says that for all A,B1,B2 ∈ C and embeddings e1 : A→B1 and e2 : A→B2 there exists C ∈ C and embeddings f1 : B1 → C and f2 : B2 →C such that f1e1 = f2e2. We call C the amalgam of B1 and B2 over A. When we can always amalgamate such that f1(B1)∩ f2(B2) = f1(e1(A)), we say that C is a strong amalgamation class. A structure A is called homogeneous (sometimes ultra-homogeneous [Hodges, 1997]) if every isomorphism between finite substructures of A can be extended to an automorphism of A. The most famous example of a homogeneous structure is given by the rationals

(as an ordered set). In fact, each order isomorphism between finite subsets can be extended to an automorphism on the rationals. Moreover, the set of all finite linear orders forms an amalgamation class.

Theorem 1 (Fra¨ıss´e 1954; see also [Hodges, 1997]). A countable class C of finite relational structures with countable signature is the age of a countable homogeneous structure B if and only if C is an amalgamation class. In this case B is up to isomorphism unique and called the Fra¨ıss´e limit of C.

A relational structure B (i.e., a structure for a purely relational signature) is called ω-categorical if all countable models of the first-order theory 1 of B are isomorphic to each other. Homogeneous structures provide a rich source of ωcategorical structures.

Proposition 1 (see [Hodges, 1997]). A countable homogeneous B over a finite relational signature is ω-categorical.

4 AHomogeneous Representation for RCC8

In this section we construct a homogeneous representation for RCC8. In this context, a representation for RCC8 is an RCC8 model that is extensional, i.e., it has the RCC8 composition table as its composition table. The relevance of homogeneous representations in the context of relation algebras and constraint satisfaction has first been recognized in [Hirsch, 1997], where such representations are described for several fundamental relation algebras such as Allen's interval algebra and the containment algebra.

We will use PP(x,y) as a shortcut for the relation defined by NTPP(x,y) ∨TPP(x,y), P(x,y) as a shortcut for the relation defined by PP(x,y)∨EQ(x,y) (which is equivalent to our previous settings), and Pi and PPi to denote the converses of these relations. In this section, τ denotes the signature of RCC8 base relations. The structure R will be defined as the Fra¨ıss´e limit of an appropriate class of finite τ-structures R.

Definition 3. The class R is the class of all finite τ-structures A that satisfy conditions (a) - (d) of Definition 2 as well as the following universally quantified axioms:

Lemma 1. The τ-structures in R with non-empty domain are exactly the finite RCC8 models.

Proof. We have to show that each (finite) RCC8 model implies (1) - (9). But this can easily from be seen from the RCC8 composition table (see Table 1). For example, DC(x,y)∧Pi(y,z) →DC(x,z) is implied by the entries (1,6) and (1,7) in the composition table, EC(x,y)∧P(y,z)→ EC(x,z)∨PO(x,z)∨PP(x,z) is implied by the entries (2,4) and (2,5), etc.

1 The first-order theory of a τ-structure B is the set of all τsentences that are true in B.

For the other direction, we show that any τ-structure that satisfies (1) - (9) is an RCC8 model, i.e., a model of the RCC8 composition table. There are 8 2 table entries. Three table entries contain all 8 base relations, in which case there is nothing to show. Since the relation EQ is the same as the equality relation, this leaves only 7 2 -3 = 46 table entries to verify. We identify those entries by pairs (row, column).

(1) covers the table entries (1,6), (1,7), (4,1), (5,1), and by contraposition and symmetry of DC, it also covers (1,2), (1,3), (1,4), (1,5), (2,1), (3,1), (6,1), and (7,1). (2) covers the table entries (2,4), (6,2). (3) covers the table entries (2,6), (4,2). (4) covers the table entries (2,7), (5,2), and by contraposition and double application, it also covers (2,2). (5) covers the table entries (3,4), (3,5), (6,3), (7,3), and by contraposition and symmetry of PO, also (2,3), (3,2), (3,6), (3,7), (4,3), and (5,3). (6) covers the table entries (5,4), (5,5), (6,7), and (7,7). And, by contraposition, also (4,7) and (5,6). (7) covers the table entries (4,5) and (7,6). (5) covers the table entries (4,4) and (6,6). Moreover, rules (9) and (3) jointly cover the table entry (7,5) and rules (2) and (4) jointly cover (2,5), (7,2). The fields (7,4), (6,5) are covered by (9) in combination with a contraposition of (6). The field (6,4) is covered by (9) in combination with a contraposition of (7). The field (4,6) is covered by a contraposition of (7).

Proposition 2. The class R has the amalgamation property.

Proof. Let A,B1,B2 be structures from R such that B1 = A∪{e1, . . . , ek} and B2 = A∪{ f1, . . . , fl}, where {e1, . . . , ek} and { f1, . . . , fl} are disjoint, and A is the substructure that is induced by A both in B1 and in B2. It suffices to show that there exists a τ-structure C in R with domain C = A∪ {e1, . . . ,ek, f1, . . . , fl} such that both B1 and B2 are induced substructures of C (this will in fact show that R has strong amalgamation).

Let G be the directed graph with vertex set A ∪ {e1, . . . ,ek, f1, . . . , fl} and edge set

Observe that, if there is a directed path in G from x to y that lies fully within Bi, for i ∈ {1,2}, then (x,y) ∈ EQ Bi ∪ NTPP Bi ∪TPP Bi ; this is straightforward to verify since Bi satisfies (1) - (9).

Moreover, by a straightforward induction one can show that if there is any directed path from x to y in G, for x, y ∈ Bi, then (x, y) ∈ EQ Bi ∪NTPP Bi ∪TPP Bi .

We now describe our amalgamation procedure. For each (x, z) ∈ C 2 ,

• we add (x, z) to R C if (x, z) ∈ R B1 ∪R B2 for some R ∈ τ;
• otherwise, we add (x,z) to NTPP C if there exists a directed path from x to z in G;
• otherwise, we add (x,z) to NTPPi C if there exists a directed path from z to x in G;

• otherwise, we add (x,z) to PO C if there exists a y and directed paths in G from y to x and from y to z, but not from x to z or from z to x;
• otherwise, we add (x,z) to PO C if there exists (x,y) ∈ PO B1 ∪PO B2 ∪EC B1 ∪EC B2 and a directed path from y to z in G;
• otherwise, add (x,z) to DC C .

It is clear that each pair (x,z) ∈C 2 is by termination of this procedure contained in exactly one of the relations of C. We claim that C satisfies (1) - (9), and verify item by item. In each of the following cases, we can assume without loss of generality that x ∈ {e1, . . . ,ek}, y ∈A, and z ∈ { f1, . . . , fl}.

1. Assume that (x,y) ∈ DC B1 , (y,z) ∈ Pi B2 ; we have to show that (x,z) ∈ DC C . But this follows from: (a) The pair (x,z) cannot be added to NTPP C : any path p1, . . . , ps from x to z must pass through A, say in pi. Then we must have (pi,z) ∈ NTPP B2 ∪TPP B2 and hence also (pi,y) ∈ NTPP B2 ∪ TPP B2 . Consequently, (pi,y) ∈ NTPP B1 ∪ TPP B1 , which leads to a contradiction to the assumption that B1 satisfies (1). (b) The pair (x,z) cannot be added to NTPPi C : any path p1, . . . , ps from z to x must pass through A, say in pi. Then (z, pi) ∈ NTPP B2 ∪TPP B2 and hence (pi,y) /∈ DC B2 by (9). Considering now the three vertices {pi,y,x} of B1, we reach a contradiction to the assumption that B1 satisfies (1). (c) The pair (x,z) cannot be added to PO C : if there is a vertex y′ with directed paths from y′ to x and from y′ to z, then we must have (y′ , y) ∈ NTPP B1 ∪ TPP B1 ; so we obtain a contradiction to the assumption that B1 satisfies (9). If there is (x,y′ ) ∈PO B1 and a path from y′ to z, then we also have (y′ ,y) ∈ NTPP B1 ∪TPP B1 , in contradiction to the assumption that B1 satisfies (5).
2. Arguing similarly as above, the pair (x,z) cannot be added to NTPP C since B1 satisfies (9), and not to NTPPi C since B1 satisfies (8). The pair (x,z) will then be added to PO C and therefore (2) is satisfied by x, y, z.
3. The pair (x,z) cannot be added to NTPP C since B1 satisfies (1), not to NTPPi C since B1 satsfies (8), and not to PO C since B1 satsfies (8). The pair (x,z) will then be added to DC C and therefore (3) is satisfied by x, y, z.
4. The argument here is the same as the argument in the previous item.
5. If the pair (x,z) has been added to NTPP C then x,y,z satisfy (5). It cannot be added to NTPPi C since B1 satisfies (8). So, if (x,y) has not been added to NTPP C , then it must have been added to PO C and (5) is again satisfied by x, y, z.
6. (x, z) has been added to NTPP C , hence (6) is satisfied.
7. (x, z) has been added to NTPP C , hence (7) is satisfied.
8. (x, z) has been added to NTPP C , hence (8) is satisfied.
9. If (x,z) is added to NTPP C or NTPPi C , then (9) is satisfied. Otherwise, it will be added to PO C and again (9) is satisfied by x, y, z in C.

In terms of constraint networks, the amalgamation property can be restated as follows: A scenario of a constraint network C is complete, atomic, and satisfiable refinement of C. If C has a scenario, then it is obviously satisfiable. Note that for many classes of RCC8 models, satisfiability for atomic networks can be decided by the path consistency procedure. It is clear that each finite RCC8 model of a network C defines a scenario of C, and conversely, that each scenario of C defines an RCC8 model of C. Let S1 and S2 be scenarios of constraint networks C1 = 〈V1,A1, l1〉 and C2 = 〈V2,A2, l2〉, respectively, that coincide on V1 ∩V2. The RCC8 model induced by S1 on the variable set V1 ∩V2, then, can be embedded into both the RCC8 models induced by S1 and S2. Hence the amalgam of these models is an RCC8 structure that satisfies all constraints in S1 and S2, and hence it induces a scenario of the constraint network C1 ∪C2.

Theorem 2. RCC8 has a representation by a countably infinite homogeneous structure R. All finite (in fact, all countable) RCC8 models embed into R.

Proof. Let R be the Fra¨ıss´e-limit of R (see e.g. [Hodges, 1997]). The Fra¨ıss´e-limit is always homogeneous; since R has a finite relational signature, it is also ω-categorical (see e.g. [Hodges, 1997]). Since all structures A in R have pairwise disjoint relations that cover all of A 2 , the same is true for R. Similarly, it is clear that R satisfies (1)-(9). Note that all the formulas to be verified for R are universal: a structure satisfies a universal formula if and only if the formula is satisfied in all finite substructures. Lemma 1 implies that R is an RCC8 model. It is also well-known that the Fra¨ıss´e-limit of a class embeds all countable structures that have the same age as the Fra¨ıss´e-limit (Lemma 6.1.3 and 6.1.4 in [Hodges, 1997]). Homogeneity of R implies that R is extensional.

5 Networks of Bounded Treewidth

Let G = 〈V,E〉 be a graph. A tree decomposition of G is a pair 〈X,T〉, where X = {X1, . . . ,Xn} is a family of subsets of V (called bags), and T is a tree with node set X such that (a) for each edge (v,w) in G, {v,w} ⊆ Xi for some bag Xi, and (b) for each path Xi T . . . T Xj T . . . T Xk in X, it holds Xi ∩Xk ⊆ Xj . The width of a tree decomposition is defined as maxi(|Xi|)-1. The treewidth of a graph G is the minimum width possible for arbitrary tree decompositions of G. Note that trees have treewidth one. The treewidth of a constraint network N is simply the treewidth of the underlying graph of N, i.e., the graph on the nodes of the network where two nodes are joined if and only if there is a constraint on those two nodes.

Let B be a structure with a finite relational signature τ , and let A be an instance of the CSP for B. Then the constraint graph of A is the graph with vertices A where two vertices are joined if there exists a tuple in a relation in A that contains both vertices.

Theorem 3 ([Bodirsky and Dalmau, 2008], Cor. 1). Let B be an ω-categorical structure. Then for any k, the CSP of B is polynomial-time tractable when restricted to instances whose constraint graphs have treewidth at most k.

We want to remark that for k = 2 and when B has only binary relation symbols, the algorithm applied in [Bodirsky and Dalmau, 2008] equals the path consistency procedure.

Theorem 4. For any k, the network consistency problem for RCC8 restricted to networks of treewidth at most k can be solved in polynomial time.

Proof Sketch. Consider the expansion S of R by a relation for each union of the relations from R. It is well-known that first-order expansions preserve ω-categoricity [Hodges, 1997], and so S is ω-categorical. An RCC8 constraint network N can be translated into an instance A of CSP(S) in the obvious way. If N has a solution, then it clearly also has a solution over a finite RCC8 model, and A homomorphically maps to S by Theorem 2. Conversely, if A homomorphically maps to S, then N is satisfiable. The result follows from Theorem 3.

Remark. In order to apply the algorithm used in Theorem 4, it is not necessary to determine the treewidth of the input network, which is in general an NP-hard problem; rather, it is sufficient to know that its treewidth is bounded.

Acknowledgments

M. B. acknowledges support from the European Research Council under the European Community's Seventh Framework Programme (FP7/2007-2013 Grant Agreement no. 257039). S.W. acknowledges support by Deutsche Forschungsgemeinschaft (SFB/TR 8 Spatial Cognition, project R4-[LogoSpace]). We thank the reviewers for their valuable comments. We also thank Till Mossakowski for discussions on an early version of the paper.