2 Preliminaries

A (binary) qualitative temporal or spatial constraint language is based on a finite set B of jointly exhaustive and pairwise-disjoint relations defined on a domain D (Ladkin & Maddux, Reference Ladkin and Maddux1994), called the set of base relations. The base relations of the set B of a particular qualitative constraint language can be used to represent the definite knowledge between any two entities with respect to the given level of granularity. B contains the identity relation Id, and is closed under the converse operation (⁻¹). Indefinite knowledge can be specified by a union of possible base relations, and is represented by the set containing them. Hence, 2^B represents the total set of relations. 2^B is equipped with the usual set-theoretic operations (union and intersection), the converse operation, and the weak composition operation denoted by ◊ (Renz & Ligozat, Reference Renz and Ligozat2005). The converse of a relation is the union of the converses of its base relations, in particular, for every r ∈ 2^B, we have that r ⁻¹={b ⁻¹ | b ∈ r}. The weak composition (◊) of two base relations b, b′ ∈ B is defined as the strongest relation r ∈ 2^B that contains b ○ b′, or, formally, b ◊ b′={b′′ ∈ B | b′′ ∩ (b ○ b′) ≠ ∅}, where b ○ b′ = {(x, y) ∈ D×D | ∃z ∈ D such that (x, z) ∈ b ∧ (z, y) ∈ b′} is the relational composition of b and b′. For every r, r′ ∈ 2^B, we have that r ◊ r′={b ◊ b′ | b ∈ r, b′ ∈ r′}.

The set of base relations of RCC-8 (Randell et al., Reference Randell, Cui and Cohn1992) is the set {dc, ec, po, tpp, ntpp, tppi, ntppi, eq}. These eight relations represent the binary topological relations between regions that are non-empty regular closed subsets of some topological space, that is, for any spatial region X we have that X=c(i(X)), where i(·) specifies the topological interior of a spatial region and c(·) the topological closure (Renz, Reference Renz2002a). The eight base relations of RCC-8 are depicted in Figure 1 (for the two-dimensional case). The set of base relations of IA (Allen 1981) is the set {eq, p, pi, m, mi, o, oi, s, si, d, di, f, fi}. These 13 relations represent the possible relations between time intervals, as depicted in Figure 2.

Figure 1 The base relations of the Region Connection Calculus (RCC)-8 constraint language

Figure 2 The base relations of the Interval Algebra constraint language

The weak composition operation ◊ along with the converse operation ⁻¹, and the total set of relations 2^B along with the identity relation Id of a qualitative constraint language, form an algebraic structure (2^B, Id, ◊, ⁻¹) that can correspond to a relation algebra in the sense of Tarski (Reference Tarski1941). This topic has been extensively discussed in Dylla et al. (Reference Dylla, Mossakowski, Schneider and Wolter2013). In fact, Dylla et al. (Reference Dylla, Mossakowski, Schneider and Wolter2013) summarizes findings on the relationship between relation algebras and some well-known qualitative constraint languages into the following result:

Networks of IA and RCC-8 can be modeled as particular instances of QCNs, with relation eq being the identity relation Id in both cases. A QCN is formally defined as follows:

Note that we always regard a QCN as a complete network. In what follows, given a QCN $${\cal N}{\equals}(V,\,C)$$ and v, v′ ∈ V, the relation C(v, v′) will sometimes be denoted by C _vv′ for simplicity. The constraint graph of a QCN $${\cal N}{\equals}(V,\,C)$$ is the graph (V, E), denoted by $${\rm G}({\cal N})$$ , for which we have that (v, v′) ∈ E iff C(v, v′) ≠ B and v ≠ v′. (B corresponds to the universal relation, that is, the non-restrictiveFootnote ² relation that contains all base relations, thus, it does not really pose a constraint.) Given a QCN ${\cal N}{\equals}(V,C),\,{\cal N}$ is said to be trivially inconsistent iff ∃v, v′ ∈ V with C(v, v′) = ∅. Further, $${\cal N}\!\downarrow \!v'$$ , with V′ ⊆ V, is the QCN $${\cal N}$$ restricted to V′. A solution of $${\cal N}$$ is a mapping σ defined from V to the domain D, yielding a valid configuration, such that ∀v, v′ ∈ V we have that (σ(v), σ(v′)) can be described by C(v, v′), that is, there exists a base relation b ∈ C(v, v′) such that (σ(v), σ(v′)) ∈ b, viz. (σ(v), σ(v′)) satisfies base relation b.

A sub-QCNFootnote ³ $${\cal N}'$$ of $${\cal N}{\equals}(V,\,C)$$ , denoted by $${\cal N}'\subseteq\,{\cal N} $$ , is a QCN (V, C′) such that C′(v, v′) ⊆ C(v, v′) ∀v, v′ ∈ V. If b is a base relation, {b} is a singleton relation. An atomic QCN is a QCN where each constraint is a singleton relation. A scenario $${\cal S}$$ of $${\cal N}$$ is a satisfiable atomic sub-QCN of $${\cal N}$$ . Given a QCN $${\cal N}{\equals}(V,\,C)$$ , a base relation b ∈ C(v, v′), with v, v′ ∈ V, is feasible (resp. infeasible) iff there exists (resp. there does not exist) a scenario $${\cal S}{\equals}(V,\,C')$$ of $${\cal N}$$ such that C′(v, v′)={b}.

Given a QCN $${\cal N}{\equals}(V,\,C)$$ , we say that a relation C(v, v′), with v, v′ ∈ V, is non-redundant in $${\cal N}$$ , if there exists a base relation b ∉ C(v, v′) and a solution σ of the QCN $${\cal N}'{\equals}(V,\,C')$$ defined by C′(v, v′)=B \ C(v, v′), C′(v′, v)=B \ (C(v, v′))⁻¹, and C′(u, w)=C(u, w) ∀(u, w) ∈ (V×V) \ {(v, v′), (v′, v)} such that (σ(v), σ(v′)) ∈ b. The relation is called non-redundant, because if we were to remove it and effectively replace it with relation B, the solution set of $${\cal N}$$ would be changed. Note that by definition every universal relation B in a QCN is redundant.

Checking the satisfiability of a QCN is ${\cal N}{\cal P}$ -complete in the general case for the most well known and interesting calculi, such as RCC-8 (Renz & Nebel, Reference Renz and Nebel1999) and IA (Nebel & Bürckert, Reference Nebel and Bürckert1995). As a direct consequence, checking if a base relation of a QCN is feasible, or if a constraint of a QCN is non-redundant, is also ${\cal N}{\cal P}$ -complete in the general case. However, there exist maximal tractable subclasses $${\cal A}\,\subseteq\,2^{{\rm B}} $$ of the considered calculi, for which the satisfiability problem becomes tractable through the use of a path-consistency Footnote ⁴ algorithm.

With respect to subclasses of relations we have the following definition:

Further, the notion of path consistency for QCNs is defined as follows:

Given a QCN $${\cal N}{\equals}(V,\,C)$$ , path consistency can be applied on $${\cal N}$$ in O(|V|³) time (Vilain et al., Reference Vilain, Kautz and Beek1990). For the calculi in this paper, we have that not trivially inconsistent and path-consistent QCNs defined over a maximal tractable subclass $${\cal A}\,\subseteq\,2^{{\rm B}} $$ are satisfiable (Nebel & Bürckert, Reference Nebel and Bürckert1995; Renz & Nebel, Reference Renz and Nebel1999)Footnote ⁵ . The maximal tractable subclasses of relations of RCC-8 and IA are the classes $$\hat{{\cal H}}_{8} ,{\cal C}_{8} ,$$ and $${\cal Q}_{8} $$ (Renz & Nebel, Reference Renz and Nebel2001) and $${\cal H}_{{{\rm IA}}} $$ (Nebel, Reference Nebel1997), respectively. Classes $$\hat{{\cal H}}_{8} $$ and $${\cal H}_{{{\rm IA}}} $$ contain exactly those relations that are transformed to propositional Horn formulas when using the propositional encodings of RCC-8 and IA, respectively. Further, and for RCC-8 in particular, if we denote by $${\cal P}_{8} $$ the set of relations that belong to either one of the classes $$\hat{{\cal H}}_{8} ,{\cal C}_{8} ,$$ and $${\cal Q}_{8} $$ , then all relations of $${\cal P}_{8} $$ not contained in $${\cal C}_{8} $$ contain $E\underline{C} $ and all relations of $${\cal P}_{8} $$ not contained in $${\cal Q}_{8} $$ contain $$E\underline{Q}$$ (Renz, Reference Renz1999). The propositional encoding of either $${\cal C}_{8} $$ or $${\cal Q}_{8} $$ is neither a Horn formula nor a Krom formula, but classes $${\cal C}_{8} $$ and $${\cal Q}_{8} $$ themselves are directly related to class $$\hat{{\cal H}}_{8} $$ in the sense that any QCN defined over either $${\cal C}_{8} $$ or $${\cal Q}_{8} $$ can be polynomially refined to a QCN defined over $$\hat{{\cal H}}_{8} $$ (Renz, Reference Renz1999).

Given two QCNs $${\cal N}{\equals}\left( {V,\,C} \right)$$ and ${\cal N}'{\equals}\left( {V',\,C'} \right)$ , we have that $${\cal N}{\cup}{\cal N}'$$ yields the QCN $${\cal N}''{\equals}\left( {V'',\,C''} \right)$$ , where V′′=V ∪ V′, C′′(u, v)=C′′(v, u)=B for all (u, v) ∈ (V \ V′) × (V′ \ V), C′′(u, v)=C(u, v) ∩ C′(u, v) for every u, v ∈ V ∩ V′, C′′(u, v)=C(u, v) for all (u, v) ∈ (V×V) \ (V′×V′), and C′′(u, v)=C′(u, v) for all (u, v) ∈ (V′×V′) \ (V×V).

We now recall the definition of the patchwork property that was originally introduced in Lutz and Milicic (Reference Lutz and Milicic2007) and was shown to be satisfied by IA and RCC-8 for satisfiable atomic QCNs of their relations.

Huang showed that IA and RCC-8 have patchwork for certain satisfiable non-atomic QCNs of their relations as well (Huang, Reference Huang2012). In particular, we have the following proposition:

Other qualitative constraint languages known to have patchwork for some subclass of their relations are listed in Huang (Reference Huang2012). Notably, those languages include the languages listed in Property 1.

Intuitively, patchwork ensures that the combination of two satisfiable constraint networks that agree on their common part, that is, on the constraints between their common variables, continues to be satisfiable. As an example, we can view the two QCNs of RCC-8 in Figure 3. (Self-loops corresponding to singleton relation {EQ} and converses of constraints are not shown for simplicity.) The QCNs of RCC-8 are atomic, as they comprise singleton relations, and are also path consistent, therefore, by Proposition 1 and application of the patchwork property, their union is satisfiable, since they agree on the constraints between their common variables, namely, on C ₀₂={DC}. (The universal relation that exists by definition between variables 1 and 3 in the unified QCN would result to relation C ₁₃={EC} if we were to calculate it, but it is not necessary to do so unless required by the specifics of the use case at hand.)

Figure 3 Patching two qualitative constraint networks of Region Connection Calculus (RCC)-8 that agree on their common part

Patchwork is closely related to the global consistency property (Renz & Ligozat, Reference Renz and Ligozat2005), which is defined as follows in Dechter (Reference Dechter2003):

In particular, global consistency implies patchwork, but the opposite is not true. For example, even though RCC-8 has patchwork (Huang, Reference Huang2012), it does not have global consistency (Renz & Ligozat, Reference Renz and Ligozat2005). For instance, let us consider the spatial configuration shown in Figure 4(a). Region y is a doughnut, and region x is externally connected to it, by occupying its hole. Further, region z is externally connected to region y. With respect to RCC-8, we know that the constraint network defined by the set of constraints {EC(x, y), EC(y, z), EC(x, z)} is satisfiable, as it is path consistent and atomic. However, the valuation of region variables x and y is such that it is impossible to extend it with a valuation of region variable z so that EC(x, z) may hold. Patchwork allows us to disregard any partial valuations and focus on the satisfiability of the network. Then, we can consider a valuation that satisfies the constraint network. Such a valuation is, for example, the one presented in Figure 4(b) along with its corresponding scenario.

Figure 4 Region Connection Calculus (RCC)-8 configurations. (a) a configuration where EC(x,z) does not hold; (b) a configuration where EC(x,z) holds, along with its corresponding scenario

3 Tree decomposition and chordal graph

The utility of taking advantage of the structure of QCNs has already been addressed in the context of heuristics for the path-consistency algorithms in Beek and Manchak (Reference Beek and Manchak1996) and Renz (Reference Renz2002b). In particular, the heuristics proposed in Renz (Reference Renz2002b) target the denser parts of the underlying constraint graph of a given QCN, that is, the qualitative relations that consist of few base relations, as an effort to propagate constraints more efficiently and also possibly resolve any local inconsistencies faster. Pruning infeasible base relations off a qualitative relation that already comprises very few base relations can almost immediately unveil an inconsistency. However, these heuristics always consider a complete underlying constraint graph of a given network. As such, they fail to completely isolate parts of the underlying constraint graph of a given QCN that are irrelevant to the process of satisfiability checking; such parts being universal relations that do not belong to the clusters of a tree decomposition corresponding to the constraint graph of the QCN at hand.

In this section, we recall the notions of a tree decomposition and a chordal graph, and review their use and effect in QSTR in combination with patchworkFootnote ⁶ . We will show that it is possible to omit satisfiability checks across clusters of a tree decomposition corresponding to the constraint graph of a QCN.

In what follows, we consult the book of Diestel on Graph Theory for related definitions and properties (Diestel, Reference Diestel2012). A tree decomposition is formally defined as follows:

Let us view the example presented in Figure 5. In the upper part of the figure we can view a graph G=(V, E), which can correspond to the structure of a constraint graph of a QCN. For the moment, we consider only the solid edges to be part of G and we disregard the dashed edges (3, 4) and (4, 5). A tree decomposition of G comprises a tree T=(I, F) and a cluster X _i for every node i ∈ I of that tree as shown in the lower part of the figure, for example, X _a ={0, 1, 2}.

Figure 5 A graph (upper part) and its tree decomposition (lower part)

Tree decompositions have been explicitly introduced in qualitative reasoning by Condotta and D’Almeida (Reference Condotta and D’Almeida2011), and implicitly by Li et al. (Reference Li, Huang and Renz2009) and Huang et al. (Reference Huang, Li and Renz2013). (The work presented in Huang et al. (Reference Huang, Li and Renz2013) properly contains the work presented in Li et al. (Reference Li, Huang and Renz2009), thus, we will stick to the former reference in what follows.)

In Condotta and D’Almeida (Reference Condotta and D’Almeida2011), the authors apply path consistency on the clusters of a tree decomposition of the constraint graph of a QCN. The graphs induced by the clusters of the tree decomposition are completed with the introduction of a new set of edges, called fill edges, that correspond to the universal relation for a QCN. These fill edges for the example graph of Figure 5 are edges (3, 4) and (4, 5). As such, the clusters of the tree decomposition are considered to be cliques, namely, sets of vertices such that every two vertices in a set are connected by an edge. This is done for two reasons: (i) by definition path consistency considers all triples of variables of a given constraint network and, hence, involves a complete graph, and (ii) the common vertices between any two complete graphs induce a complete graph, thus, the corresponding constraint networks will completely agree on the constraints between their common variables and the patchwork property can be used. The patchwork property is then considered to patch together the not trivially inconsistent and path-consistent pre-convex QCNs of IA (Ligozat, Reference Ligozat2011) that correspond to the graphs induced by the clusters of the tree decomposition in a tree-like manner and construct a satisfiable network.

In Huang et al. (Reference Huang, Li and Renz2013), the authors enlist a structure known as a dtree (decomposition tree), which, as the name suggests, is very close to a tree decomposition. Without going further into detail, a dtree is a full binary tree where the root represents a given graph and for each non-leaf node its two children represent a partitioning of the parent graph into two subgraphs. Thus, although a dtree is not a tree decomposition, it provides a way to construct a tree decomposition out of a given graph. A dtree and a tree decomposition are therefore equivalent in the context of qualitative reasoning, since omitting path consistency checks across children of dtree nodes (as described in Huang et al. (Reference Huang, Li and Renz2013)) corresponds to omitting those checks across clusters of the tree decomposition into which the dtree is converted, as has been specifically pointed out in Condotta and D’Almeida (Reference Condotta and D’Almeida2011). Similar to what is done in Condotta and D’Almeida (Reference Condotta and D’Almeida2011), children of dtree nodes are treated as cliques, and the patchwork property is considered to patch together the path-consistent atomic QCNs of either IA or RCC-8 in a tree-like recursive manner and construct a satisfiable network.

The observant reader will note that it would be convenient to operate directly on a tree decomposition (T, X) of a given graph G where X would be a collection of cliques. In this context, chordal graphs become relevant. Formally, a chordal graph is defined as follows:

We then have the following proposition:

For example, the graph presented in Figure 5, with the dashed edges included, is chordal. Chordality checking can be done in (linear) O(|V|+|E|) time for a given graph G=(V, E) with the maximum cardinality search algorithm, which also constructs an elimination ordering ω as a by-product (Tarjan & Yannakakis, Reference Tarjan and Yannakakis1984). If a graph is not chordal, it can be made so through the addition of fill edges. This process is usually called triangulation of a given graph G=(V, E) and can run as fast as in O(|V|+(|E ∪ F(ω)|)) time, where F(ω) is the set of fill edges that results by following the elimination ordering ω, eliminating the nodes one by one, and connecting all nodes in the neighborhood of each eliminated node, thus, making it simplicial in the resulting subgraph. If the graph is already chordal, following the elimination ordering ω produced by the maximum cardinality search algorithm guarantees that no fill edges are added, that is, ω is actually a perfect elimination ordering (Diestel, Reference Diestel2012). For example, a perfect elimination ordering for the chordal graph shown in Figure 5 would be the ordering 0 → 1 → 2 → 3 → 4 → 7 → 5 → 6 → 9 → 8 → 10 of its set of nodes. In general, it is desirable to achieve chordality with as few fill edges as possible. However, triangulating a graph with the minimum number of fill edges is known to be ${\cal N}{\cal P}$ -complete (Yannakakis, Reference Yannakakis1981). As noted earlier, fill edges correspond to the universal relation for a QCN. As such, the chordal constraint graph of a given QCN is exactly its constraint graph augmented with constraints corresponding to the universal relation to make it chordal.

In light of Propositions 1 and 2, research efforts focused on making the constraint graph of a given QCN chordal and restricting path consistency to that chordal graph, while fully utilizing maximal tractable subclasses of relations and not just base relations that are typically used to describe only atomic networks. Toward this direction, we have the works of Chmeiss and Condotta (Reference Chmeiss and Condotta2011) for IA and Sioutis and Koubarakis (Reference Sioutis and Koubarakis2012) for RCC-8. These works were later combined in Amaneddine et al. (Reference Amaneddine, Condotta and Sioutis2013) to give the following result, which is the strongest yet concerning path consistency, patchwork, and subclasses of relations:

Consequently, by Propositions 1 and 3 we have the following result:

Proposition 3 generalizes the results of all the works that were discussed earlier in this section and make use of path consistency as the main tool for checking the satisfiability of a given QCN, and has a great effect in the efficiency and scalability of practical reasoning. In particular, regarding native search, an algorithm based on the work of Bliek and Sam-Haroud (Reference Bliek and Sam-Haroud1999) was devised, called partial path consistency (Chmeiss & Condotta, Reference Chmeiss and Condotta2011), that enforces partial path consistency on a given QCN $${\cal N}{\equals}(V,\,C)$$ with respect to a triangulation G=(V, E) of its constraint graph in O(δ|E|) time, where δ is the maximum vertex degree of G.

The partial path-consistency algorithm of Chmeiss and Condotta is presented in Algorithm 1. As it is suggested in Proposition 3, the partial path-consistency algorithm is able to decide the satisfiability of a QCN defined over some subclass of relations, when path consistency can yield patchwork with respect to that subclass of relations, and when a triangulation of its constraint graph is used as the input graph in the algorithm.

The search space for intractable Gs was also reduced to O(α ^|E| from $$O(\alpha ^{{\left| V \right|^{2} }} )$$ for a backtracking algorithm (Renz & Nebel, Reference Renz and Nebel2001), where α is the branching factor provided by some subclass of relations (e.g. α=1.4375 for class $$\hat{{\cal H}}_{8} $$ of RCC-8 (Renz & Nebel, Reference Renz and Nebel2001)). Such a backtracking algorithm is presented in Algorithm 2. Note that if a QCN $${\cal N}$$ along with a triangulation G of its constraint graph and a subclass $${\cal A}$$ are given as input to the backtracking algorithm, then the algorithm is able to decide the satisfiability of the given network $${\cal N}$$ provided that path consistency can yield patchwork with respect to $${\cal A}$$ .

Regarding approaches based on encodings of QCNs into Boolean formulas, that is, Boolean Satisfiability Problem (SAT)-based approaches, the implication of Proposition 3 led to significant memory and speed improvements both for IA- (Westphal et al., Reference Westphal, Hué and Wölfl2013) and for RCC-8 (Westphal & Hué, Reference Westphal and Hué2014) targeted implementations. Further, regarding works that consider the MLP and the redundancy problem of a QCN, partial path consistency has been used as the core local consistency condition to build algorithms both for the MLP as described in Amaneddine et al. (Reference Amaneddine, Condotta and Sioutis2013) and for the redundancy problem as described in Sioutis et al. (Reference Sioutis, Li and Condotta2015b).

Before closing this section with some strong theoretical results that concern tree decompositions and patchwork, let us introduce the treewidth of a graph. The width of a tree decomposition (T, {X ₁, … , X _n } is $$\mathop{{{\rm max}}}\limits_{{1\, \les\, i \,\les \,n}} \,\mid\!X_{i} \!\mid\,{\minus}1$$ . The treewidth of a graph G is the minimum width possible among all tree decompositions of G. We also recall the following result regarding the treewidth of a graph G that is augmented with a new edge:

In the context of QCNs, the treewidth of a QCN $${\cal N}$$ is simply the treewidth of its constraint graph $${\rm G}({\cal N})$$ .

Consequently, by Proposition 1 and Theorem 2 we have the following result:

A detailed algorithm for Theorem 2 that offers an alternative to the proof sketch of Bodirsky and Wölfl (Reference Bodirsky and Wölfl2011) is provided in Huang et al. (Reference Huang, Li and Renz2013). (The proof sketch in Bodirsky & Wölfl (Reference Bodirsky and Wölfl2011) is particular to RCC-8, but it can be generalized to IA and other languages satisfying certain common properties, such as patchwork.)

Further, regarding the MLP we can have the following result:

Proof. Let $${\cal N}{\equals}(V,\,C)$$ be a QCN of treewidth at most k that is defined on a language that has patchwork for path-consistent atomic QCNs. To check if a base relation b ∈ C(u, v), with $$(u,\,v)\in{\rm G}({\cal N})$$ , participates in at least one solution of $${\cal N}$$ , we must check if the QCN $${\cal N}'{\equals}(V,\,C')$$ defined by C′(u, v)={b}, C′(v, u)={b}⁻¹, and C′(y, w)=C(y, w) ∀(y, w) ∈ (V×V) \ {(u, v), (v, u)} is satisfiable, so that a scenario S=(V, C′′) with C′′(u, v)={b} can be constructed out of the admitted solution. This satisfiability check can be done in polynomial time by Theorem 2. Note that if $$(u,\,v)\,\notin\,{\rm G}({\cal N})$$ , we must augment the constraint graph $${\rm G}({\cal N})$$ with (u, v) to take into account the constraint C(u, v). As such, the satisfiability check will be performed on a QCN of treewidth at most k+1 due to Theorem 1. (After the check, (u, v) can again be removed from $${\rm G}({\cal N})$$ .) As we can have at most O(|B||V|²) base relations in any given QCN, it follows that we can solve the MLP in polynomial time.□

Consequently, by Proposition 1 and Theorem 3 we have the following result:

Regarding the redundancy problem, we can have the following result:

Proof. Let $${\cal N}{\equals}(V,\,C)$$ be a QCN of treewidth at most k that is defined on a language that has patchwork for path-consistent atomic QCNs. To check if a constraint C(u, v), with $$(u,\,v)\in{\rm G}({\cal N})$$ , is non-redundant in $${\cal N}$$ , we must check if there exists a base relation b ∉ C(u, v) that participates in a solution of the modified $${\cal N}$$ that results by removing C(u, v). This is equivalent to checking if the QCN $${\cal N}'{\equals}(V,\,C')$$ defined by C′(u, v)=B \ C(u, v), C′(v, u)=B \ (C(u, v))⁻¹, and C′(y, w)=C(y, w) ∀(y, w) ∈ (V×V) \ {(u, v), (v, u)} is satisfiable. This satisfiability check can be done in polynomial time by Theorem 2. (Note that if $$(u,\,v)\,\notin\,{\rm G}({\cal N})$$ , C(u, v) is by definition redundant.) Since we can have at most O(|V|²) constraints in any given QCN, it follows that we can solve the redundancy problem in polynomial time.□

Consequently, by Proposition 1 and Theorem 4 we have the following result:

4 Partitioning graph

In this section, we prove that the decomposition-based approach presented in Nikolaou and Koubarakis (Reference Nikolaou and Koubarakis2014) for checking the satisfiability of QCNs of RCC-8 lacks soundness, as the notion of a partitioning graph defined in that work is not coherent with the use of patchwork upon which it solely relies, in two ways, which we enumerate and analyze in the form of issues.

Let G=(V, E) be a graph and k a positive integer. If U ⊆ V, then G(U) will denote the subgraph of G that is induced by the set of vertices U. A set {V _i ⊆ V | 1⩽i⩽k} with k pairwise-disjoint elements such that $\mathop{{\cup}}\limits_{{i{\equals}1}}^{k} V_{i} {\equals}V$ , is called a k-way partitioning of G. Finally, let Ø denote the empty, edgeless, graph. We recall the following definition of a partitioning graph from Nikolaou and Koubarakis (Reference Nikolaou and Koubarakis2014):

Let G be a graph and P=(V _P , E _P , λ _P , G _P ) one of its partitioning graphs. Then, an edge e of G present in more than one subgraph G _i ∈ G _P is called a global edge. An edge e of G present in exactly one subgraph G _i ∈ G _P is called a local edge.

We will now enumerate the issues that lead to non-soundness and provide counter-examples for each case. The reader is kindly asked to refer to Nikolaou and Koubarakis (Reference Nikolaou and Koubarakis2014) and check that the flaws pointed out here are actually present in Nikolaou and Koubarakis (Reference Nikolaou and Koubarakis2014).

The issues that we will enumerate will allow us to infer the following fact:

We begin with the first issue.

Issue 1. The first issue has to do with the fact that a complete agreement on the constraints between the common variables of two networks is not achieved in order to allow the applicability of patchwork. Let us consider the example of Figure 6. Graph G is partitioned into two parts, namely, G ₁ and G ₂. The partitioning graph is shown in the lower part of the figure, and it comprises the set of nodes {a, b} and an empty set of edges. Node a corresponds to subgraph G ₁ and node b to subgraph G ₂. Its set of edges E _P is empty as subgraphs G ₁ and G ₂ do not share a common edge (that would otherwise be the global edge (0, 2)), thus, the only possible edge (a, b) does not exist. In Nikolaou and Koubarakis (Reference Nikolaou and Koubarakis2014), the authors perform path consistency on the subgraphs of a graph separately, in a parallel fashion, and then rely on the set of edges E _P to identify the subgraphs among which a complete agreement has to be ensured (the reader is kindly asked to refer to line 7 in the function of Algorithm 2 in Nikolaou & Koubarakis (Reference Nikolaou and Koubarakis2014)). If, as in this example, such an edge does not exist, a complete agreement is never achieved. This can be the cause of failing to identify inconsistencies. Let us assume that graph G, as depicted in Figure 8, is the constraint graph of a given QCN comprising constraints C ₀₁=C ₁₂=C ₂₃=C ₃₀={TPP}. This yields an unsatisfiable network, as it basically infers that region 0 is properly contained in region 2, and vice versa. Applying path consistency on that network would result in the empty relation assignment for constraint C ₀₂ (inconsistency). However, that constraint is never checked in our example. Although the authors implicitly complete subgraphs G ₁ and G ₂ in order to apply path consistency, they do not complete these subgraphs when computing their intersection, as clearly specified in the last bullet of Definition 12. Even if they did implicitly consider complete subgraphs for that part of the definition, and the edge (a, b) indeed existed, line 7 in the function of Algorithm 2 in Nikolaou and Koubarakis (Reference Nikolaou and Koubarakis2014) still requires that an agreement should only be achieved for every common edge of G ₁ and G ₂ (the initial non-complete subgraphs), which is none. If they implicitly considered complete subgraphs for that part of the algorithm too, then this particular issue for a two-way partitioning would be resolved. We have also verified this issue experimentally with the implementation used in Nikolaou and Koubarakis (Reference Nikolaou and Koubarakis2014)Footnote ⁷ .

Figure 6 A graph and its partitioning graph with the parts comprising it (also contained in dashed circles in the initial graph)

Before proceeding to the next issue, let us assume that the first issue is fixed with everything that we propose, and a two-way partitioning is actually valid for applying patchwork. We mean to show that the concept of a partitioning graph is beyond repair, unless it is structured in a way that it defines a tree decomposition, which defeats the purpose of having to define a partitioning graph in the first place.

The second issue follows.

Issue 2. This issue has to do with the fact that even if the first issue is resolved, the partitioning graph can suffer from the existence of cycles that are created by subgraphs of a given graph. Let us consider the example of Figure 7. Graph G is partitioned into four parts, namely, G ₁, G ₂, G ₃, and G ₄. The partitioning graph is shown in the lower part of the figure, and the correspondence between its sets of nodes and edges with the different subgraphs should be clear up to this point. Note that all subgraphs are complete, thus, they completely overlap with each other on the common vertices. For example, graph G ₁ completely overlaps with graph G ₂ on the edges of the graph defined on the single common vertex 0, as their intersection yields the complete graph on single vertex 0. Although such an overlap is trivial, as a complete graph on a single vertex (singleton graph) does not have any edges, it is sufficient to ensure the applicability of patchwork for the corresponding constraint networks. (Our example can be easily extended to non-trivial overlaps.) However, due to the last bullet of Definition 12, the partitioning graph is unable to obtain any edges, as there can exist no global edges. In fact, even if some edges existed in E _P , in any possible combination and amount, the partitioning graph would still fail to detect the cycle that is constructed by the complete subgraphs G ₁, G ₂, G ₃, and G ₄, namely, the cycle defined by vertices 0, 1, 2, and 3. This cycle, as shown in the example of Figure 6, can harbor an inconsistency. Such a cycle exists also in Nikolaou and Koubarakis (Reference Nikolaou and Koubarakis2014, figure 1) between vertices 3, 4, 5, and 7 there. Patchwork alone is only valid for tree decompositions, as tree decompositions guarantee acyclicity of cliques and, thus, do not harbor cycles with potential inconsistencies that cannot be detected by the application of path consistency on the different cliques. This issue was again verified experimentally.

Figure 7 A graph and its partitioning graph with the parts comprising it (also contained in dashed circles in the initial graph)

Essentially, the approach defines a partial algorithm; a given satisfiable QCN will be shown to be satisfiable, as the approach in Nikolaou and Koubarakis (Reference Nikolaou and Koubarakis2014) because disregarding constraints operates on a less restrictive constraint graph of the input network where constraint propagation and consistency checks are limited, whilst an unsatisfiable QCN may be shown to be satisfiable.

5 Toward efficient utilization of parallelism

As noted in Nikolaou and Koubarakis (Reference Nikolaou and Koubarakis2014), the authors provided a parallel implementation for checking the satisfiability of a QCN of RCC-8, which however lacks soundness (Proposition 4). In this section, we present a simple decomposition scheme that exploits the sparse and loosely connected structure of the constraint graphs of very large real-world QCNs, which have been of notable interest in the recent literature (Nikolaou & Koubarakis, Reference Nikolaou and Koubarakis2014; Sioutis, Reference Sioutis2014; Sioutis & Condotta, Reference Sioutis and Condotta2014), and paves the way for efficient utilization of parallelism. Our approach is based on extracting the smaller QCNs that correspond to the biconnected components of the constraint graph of a given large QCN and reasoning with these smaller biconnected QCNs completely separately, in a parallel or serial fashion, which, as our experimentation suggests, significantly decongests search when solving intractable QCNs.

First, we recall a definition from Dechter (Reference Dechter2003) regarding biconnected graphs and components.

Intuitively, an articulation vertex is any vertex whose removal increases the number of connected components in a given graph. From Dechter (Reference Dechter2003), we also have the following property:

Let us now view the discussed notions in an example. Figure 9 depicts a graph G, along with its biconnected components, and its tree decomposition. Vertices in gray color are the articulation vertices of G. The tree decomposition comprises a tree T=(I, F) and a cluster X _i for every node i ∈ I of that tree, for example, X _a ={v ₀, v ₁, v ₄, v ₅}. We remind the reader that $${\cal N}\downarrow_{V} $$ is the QCN $${\cal N}$$ restricted to a set of variables V. We can obtain the following proposition:

Figure 9 A graph G (top) with its biconnected components (middle) and its tree decomposition (bottom)

Proof. By Property 2, the constraint graph $${\rm G}({\cal N})$$ has a tree decomposition (T, {X ₁, … , X _k }), where cluster X _i induces G _i , for every i ∈ {1, … , k}. We can also infer by Definition 13 that ∀i, j ∈ {1, … , k} with i ≠ j, V (G _i ) ∩ V (G _j ) contains at most one vertex u. If $${\cal N}_{i} $$ is satisfiable for every i, j ∈ {1, … , k}, we can obtain a satisfiable atomic sub-QCN of $${\cal N}_{i} $$ , that is, a scenario S _i of $${\cal N}_{i} $$ , for every i ∈ {1, … , k}. For any possible scenarios and any i, j ∈ {1, … , k} with i ≠ j, we will have that $${\cal S}_{i} {\equals}(V\,(G_{i} ),\,C_{i} )$$ and $${\cal S}_{j} {\equals}(V\,(G_{j} ),\,C_{j} )$$ will always agree on the single unary constraint that is defined by a single vertex u ∈ V (G _i ) ∩ V (G _j ) whenever we have that V (G _i ) ∩ V (G _j ) ≠ ∅, that is, C _i (u, u)=C _j (u, u)={Id}, as by Definition 1 we have that for any QCN ${\cal M}{\equals}(V,\,C)$ , C(v, v)={Id} ∀v ∈ V. By Definition 7, we can apply patchwork to patch together all the satisfiable atomic QCNs $${\cal S}_{i} $$ with i ∈ {1, … , k} in a tree-like manner and, thus, derive the satisfiability of $${\cal N}$$ . If $${\cal N}$$ is satisfiable, then, clearly, $${\cal N}_{i} $$ will be satisfiable for every i ∈ {1, … , k}.□

Consequently, by Proposition 6 and the fact that IA and RCC-8 have patchwork for satisfiable atomic QCNs of their relations (Lutz & Milicic, Reference Lutz and Milicic2007), we have the following result:

It is important to note that the proof of Proposition 6 is based on tree decompositions whose nodes correspond to clusters where any two clusters share at most one vertex with each other. In case two clusters share more than one vertex with each other, the involved QCNs should be, for instance (and among other conditions), not trivially inconsistent, path consistent, and defined over a subclass of relations of a qualitative constraint language that has patchwork for not trivially inconsistent and path-consistent QCN defined over that subclass of relations, as it is specified in Proposition 3 and considered in Sioutis and Koubarakis (Reference Sioutis and Koubarakis2012) and Chmeiss and Condotta (Reference Chmeiss and Condotta2011) for RCC-8 and IA, respectively. A simple algorithm for obtaining a collection of QCNs that correspond to the biconnected components of the constraint graph of a given QCN is presented in Algorithm 3. Note that in lines 2–3 we immediately return the input QCN if it is trivially inconsistent, as it would not make any sense to continue with the decomposition procedure. Function BCSubgraphs(G) in line 4 returns the biconnected components of a graph G=(V, E) and has a runtime of O(|E|) (Dechter, Reference Dechter2003). Note that in line 4 we keep only the components of order >2, as any not trivially inconsistent QCN of <3 variables is trivially satisfiable (by definition of a base relation). In what follows, we always consider components of order >2. Based on Decomposer, we can obtain an algorithm to increase the performance of any given state-of-the-art solver that is sound and complete for checking the satisfiability of a given QCN $${\cal N}$$ defined on a language that has patchwork for satisfiable atomic QCNs; that algorithm is presented in Algorithm 4. Let us denote any such given state-of-the-art solver by Solver. Then, Algorithm 4 will use Solver to decide the satisfiability of the QCNs that correspond to the biconnected components of the constraint graph of $${\cal N}$$ . The enclosure with symbol ‖ for Solver denotes the fact that Solver can be used in a parallel or serial fashion.

Regarding the MLP, we can have the following result:

Proof. Let $${\cal N}'{\equals}(V,\,C')$$ be the QCN defined by C′(u, v)={b}, C′(v, u)={b}⁻¹, and C'(y, w)=C(y, w) ∀(y, w) ∈ (V×V) \ {(u, v), (v, u)}. Further, let $${\cal N}_{i} ^{\prime} {\equals}(V_{i} ,\,C_{i} ^{\prime} )$$ be the restriction of $${\cal N}'$$ to V (G _i ), viz., $${\cal N}'\downarrow_{{V\,(G_{i} )}} $$ . Then, by Proposition 6 and as G _i is a biconnected component of $${\rm G}({\cal N})$$ , we know that $${\cal N}'$$ is satisfiable iff $${\cal N}_{i} ^{\prime} $$ is satisfiable; in addition, any scenario $$S_{i} {\equals}(V_{i} ,\,C_{i}^{\prime\prime} )$$ of $${\cal N}_{i} ^{\prime} $$ is the restriction of some scenario S=(V, C′′) of $${\cal N}'$$ to V _i , and any scenario S=(V, C′′) of $${\cal N}'$$ is the extension of some scenario $$S_{i} {\equals}(V_{i} ,\,C_{i}^{\prime\prime} )$$ of $${\cal N}_{i} ^{\prime} $$ to V. As such, the feasibility of b can be characterized by considering $${\cal N}_{i} $$ instead of $${\cal N}$$ .□

Given a satisfiable QCN $${\cal N}{\equals}(V,\,C)$$ , Proposition 7 allows one to quickly characterize the feasibility of a base relation b ∈ C(u, v), with u, v ∈ V (G′), where G′ is a biconnected component of the constraint graph $${\rm G}({\cal N})$$ . If u, v ∉ V (G') for any biconnected component G′ of $${\rm G}({\cal N})$$ , then b belongs to a constraint that is labeled with the universal relation B and its feasibility can still be efficiently characterized under certain conditions by a function similar to extractFeasible as described in Amaneddine et al. (Reference Amaneddine, Condotta and Sioutis2013).

Consequently, by Proposition 7 and the fact that IA and RCC-8 have patchwork for satisfiable atomic QCNs of their relations (Lutz & Milicic, Reference Lutz and Milicic2007), we have the following result:

Regarding the redundancy problem, we can have the following result:

Proof. Clearly, a relation C(u,v) is redundant in $${\cal N}$$ if (u, v) ∉ E(G _i ) for any i ∈ {1, … , k}, as it will correspond to the universal relation B. Let us consider a relation C(u, v) where (u, v) ∈ E(G _i ) for some i ∈ {1, … , k}. Let $${\cal N}'{\equals}(V,\,C')$$ be the QCN defined by C′(u, v)=B \ C(u, v), C′(v, u)=B \ (C(u, v))⁻¹, and C′(y, w)=C(y, w) ∀(y, w) ∈ (V×V) \ {(u, v), (v, u)}. Further, let $${\cal N}_{i} ^{\prime} {\equals}(V_{i} ,\,C_{i} ^{\prime} )$$ be the restriction of $${\cal N}'$$ toV(G _i ), viz., $${\cal N}'\downarrow_{{V\,(G_{i} )}} $$ . Then, by Proposition 6 and as G _i is a biconnected component of $${\rm G}({\cal N})$$ , we know that $${\cal N}'$$ is satisfiable iff $${\cal N}_{i} ^{\prime} $$ is satisfiable; in addition, any scenario $$S_{i} {\equals}(V_{i} ,\,C_{i}^{\prime\prime} )$$ of $${\cal N}_{i} ^{\prime} $$ is the restriction of some scenario S=(V, C′′) of $${\cal N}'$$ to V _i , and any scenario S=(V, C′′) of $${\cal N}'$$ is the extension of some scenario $$S_{i} {\equals}(V_{i} ,\,C_{i}^{\prime\prime} )$$ of $${\cal N}_{i} ^{\prime} $$ to V _i . Finally, since for any scenario there exists a solution that satisfies all of its base relations, the redundancy of C(u, v) can be characterized by considering $${\cal N}_{i} $$ instead of $${\cal N}$$ .□

Consequently, by Proposition 8 and the fact that IA and RCC-8 have patchwork for satisfiable atomic QCNs of their relations (Lutz & Milicic, Reference Lutz and Milicic2007), we have the following result:

6 Decomposition techniques in the constraint satisfaction problem framework

As noted in our introduction, a QCN is most efficiently modeled as an infinite-domain variant of a CSP through the use of a relation algebra (Ladkin & Maddux, Reference Ladkin and Maddux1994), which is also the approach we followed in our work. However, a QCN can also be encoded as a finite CSP instance (Renz & Nebel, Reference Renz and Nebel2001; Brand, Reference Brand2004; Condotta et al., Reference Condotta, Dalmeida, Lecoutre and Sais2006). In particular, given a QCN (V, C), where |V|=n we can obtain a CSP instance as follows. Let X denote the set of variables containing a variable x _ij for each pair of variables v _i , v _j ∈ V with 1⩽i<j⩽n. Then, our instance has the form (X, B, DCon ∪ TCon), where DCon is the set of domain constraints {(x _ij , C _ij ) | 1⩽i<j⩽n} and TCon the set of ternary constraints {((x _ij , x _ik , x _kj ), R _◊) | 1⩽i<j<k⩽n} with R _◊={(b, b′, b′′) ∈ B³ | b ∈ b′ ◊ b′′}. Namely, DCon restricts the values of a variable x _ij to the base relations of the corresponding qualitative constraint C _ij and TCon encodes all the consistent paths of length 2 in the network. The resulting finite network has ${{n(n{\minus}1)} \over 2}$ variables and $\left( {\matrix{ n \cr 3 \cr } } \right)$ ternary constraints. A solution of this finite instance corresponds to a path-consistent atomic refinement of a given QCN, and vice versa (Condotta et al., Reference Condotta, Dalmeida, Lecoutre and Sais2006). The main disadvantage of this approach is that we are not able to make use of tractable subclasses of relations. This can seriously impact the performance of satisfiability checking for calculi that heavily rely upon those subclasses, such as RCC-8 and IA. However, for large-sized qualitative calculi (viz., comprising hundreds of base relations) for which no tractable subclasses are known, a finite CSP encoding can provide a considerable performance gain (Westphal & Wölfl, Reference Westphal and Wölfl2009).

In light of the strong relation that exists between qualitative and ‘traditional’ constraint programming, it is worth mentioning some works in the latter paradigm that exploit the structure of constraint graphs in a similar manner to what we presented in our paper. The interested reader may review the cited works and obtain a deeper understanding on the analogy that exists between structural characteristics of QCNs and finite CSP instances. What is more important, the cited works may drive future research by enabling the reader to identify theoretical properties in the context of QSTR that can be used to adopt certain techniques for exploiting the structure of constraint graphs that exist in constraint programming.

Walsh (Reference Walsh2001) measures the impact that the structure of a constraint graph can have on the performance of solving the graph coloring problem, which is the problem of coloring the vertices of a graph in such a way that no two adjacent vertices share the same color.

Baget and Tognetti (Reference Baget and Tognetti2001) propose a backtracking algorithm for solving CSP instances that exploits the biconnected components of a given constraint graph to reduce search space, permanently removing values and compiling partial solutions during exploitation.

Dechter and Pearl (Reference Dechter and Pearl1989) propose a constraint graph restructuring technique, based on tree decompositions, that guarantees that a large variety of queries could be answered swiftly either by sequential backtrack-free procedures, or by distributed constraint propagation methods.

Based on the work of Dechter and Pearl (Reference Dechter and Pearl1989), Jégou and Terrioux (Reference Jégou and Terrioux2003) propose a framework for solving CSP instances that relies both on backtracking techniques and on the notion of tree decomposition of the constraint graphs. Notably, this mixed approach has been implemented and used successfully for practical CSP solving (Jégou & Terrioux, Reference Jégou and Terrioux2003).

Jegou et al. (Reference Jégou, Ndiaye and Terrioux2005) study several methods for computing a rough optimal tree decomposition and assess their relevance for solving CSP instances; the same authors also proposed dynamic heuristics for efficient backtrack search on tree decompositions of constraint graphs in Jegou et al. (Reference Jégou, Ndiaye and Terrioux2006, Reference Jégou, Ndiaye and Terrioux2007).

Recently, Jégou and Terrioux (Reference Jégou and Terrioux2014a, Reference Jégou and Terrioux2014b) introduced and exploited a new graph parameter, called bag-connected treewidth, which considers tree decompositions for which each cluster induces a connected graph. It is experimentally shown in Jégou and Terrioux (Reference Jégou and Terrioux2014b) that such bag-connected tree decompositions significantly improve the solving of CSP instances by decomposition methods.

Finally, a presentation of the major structural constraint network decomposition methods discussed here is given in Gottlob et al. (Reference Gottlob, Leone and Scarcello2000).