Efficient Approach to Solve the Minimal Labeling Problem of Temporal and Spatial Qualitative Constraints

1 Introduction

Spatial and temporal reasoning is a major field of study in Artificial Intelligence; particularly in Knowledge Representation. This field has gained a lot of attention during the last few years as it extends to a plethora of areas and domains that include, but are not limited to, ambient intelligence, dynamic GIS, cognitive robotics, and spatiotemporal design [Bhatt et al., 2011; Hazarika, 2012]. In this context, an emphasis has been made on qualitative spatial and temporal reasoning which relies on qualitative abstractions of spatial and temporal aspects of the common-sense background knowledge, on which our human perspective on the physical reality is based. The concise expressiveness of the qualitative approach provides a promising framework that further boosts research and applications in the aforementioned areas and domains.

The Interval Algebra (IA) [Allen, 1981] and a subset of the Region Connection Calculus (RCC) [Randell et al., 1992], namely RCC-8, are the dominant Artificial Intelligence approaches for representing and reasoning about qualitative temporal and topological relations respectively. These qualitative calculi use constraints to encode knowledge about the spatial or temporal relationships between entities. Thus, qualitative information can be modelled as a domain-specific vari-

Michael Sioutis

Universit´e Pierre et Marie Curie Paris, France michael.sioutis@lip6.fr

ant of a Constraint Satisfaction Problem (CSP) [Montanari, 1974; Mackworth, 1991]. Infinite domains is the main difference of spatial or temporal CSPs to normal CSPs. For instance, there are infinitely many time points or temporal intervals on the time line and infinitely many regions in a two or three dimensional space. One way of dealing with infinite domains is using constraints over a finite set of binary relations, by employing a relation algebra [Ladkin and Maddux, 1994]. We will use the term QCN to refer to this particular type of infinite-domain CSP that makes use of a relation algebra to handle qualitative constraints.

Given a QCN, we are particularly interested in the consistency problem and the minimal labeling problem (MLP). The consistency problem is deciding whether a set of constraints can be satisfied simultaneously, i.e., whether there exists an interpretation of all variables such that all constraints are satisfied by this interpretation. The MLP (also known as the deductive closure problem) is determining all the feasible base relations (i.e., the base relations participating in at least one solution) for each of the constraints. These two problems in IA and RCC-8 are NP-hard in general [Vilain and Kautz, 1986; Liu and Li, 2012]. However, there exist large maximal tractable subsets of IA and RCC8 which can be used to make reasoning much more efficient even in the general NP-hard case [Nebel and B¨urckert, 1995; Renz, 1999]. In this paper, we concentrate on the MLP only.

Practical approaches to deal with the MLP in the context of qualitative spatial and temporal reasoning have mainly focused on identifying tractable subsets for which pathconsistency is sufficient to ensure minimality of a given QCN. This paradigm is well described in the works of van Beek [van Beek, 1992], Bessi`ere et. al [Bessi`ere et al., 1996], and Amaneddine et. al [Amaneddine and Condotta, 2012] for IA, and in one original work of Chandra et. al [Chandra and Pujari, 2005] for RCC-8. Here, we provide the following contributions: (i) we formally introduce and study a new form of partial consistency for QCNs, called ◆G-consistency, where G is a graph on the set of variables of a given QCN, (ii) we propose a new algorithm to solve the MLP, called Minimize, that considers QCNs with chordal constraint graphs and employs tractable subsets of relations of IA and RCC-8 that have a particular patchwork property [Lutz and Milicic, 2007; Huang, 2012], and (iii) we show the practical interest of our approach through an experimental evaluation.

The remaining parts of this paper are organized as follows: Section 2 introduces the main notions and terminology of QCNs, focusing on IA and RCC-8. In Section 3 we define ◆G-consistency and outline its connection with the MLP. Section 4 presents our new algorithm, viz., Minimize, for solving the MLP. In Section 5 we evaluate this algorithm experimentally. Finally, in Section 6 we conclude and give directions for future research.

2 Preliminaries

A (binary) temporal or spatial qualitative calculus [Renz and Ligozat, 2005] is based on a finite set B of jointly exhaustive and pairwise disjoint (JEPD) relations defined on a domain D, called base relations. The set of base relations B of a particular qualitative calculus can be used to represent 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 (-1 ). Indefinite knowledge can be specified by unions of possible base relations, and is represented by the set containing them. Hence, 2B will represent the set of relations. 2B is equipped with the usual set-theoretic operations (union and intersection), the converse operation, and the weak composition operation. The converse of a relation is the union of the converses of its base relations. The weak composition ⋄ of two relations s and t for a set of base relations B is defined as the strongest relation r ∈ 2B which contains s ◦ t, or formally, s ⋄ t = {b ∈ B | b ∩(s ◦ t) ̸= ∅}, where s ◦ t = {(x, y) | ∃z : (x, z) ∈ s ∧ (z, y) ∈ t} is the relational composition.

As illustration, consider the temporal qualitative calculus IA [Allen, 1981] and the spatial qualitative calculus RCC-8 [Randell et al., 1992]. The set of base relations of IA, denoted by BIA, is the set {eq, p, pi,m,mi, o, oi, s, si, d, di, f, fi}. These thirteen relations represent the possible relations between time intervals as depicted in Figure 1. The set of base relations of RCC-8, denoted by BRCC8, 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 subsets of some topological space as depicted in Figure 2 (for the 2D case).

A Qualitative Constraint Network (QCN) consists of a set of variables and a set of constraints. Each variable represents an entity and each constraint represents the set of possible qualitative configurations between two entities. Formally, a QCN is defined as follows:

Definition 1 A QCN is a pair N = (V, C) where: V is a non empty finite set of variables; C is a mapping that associates a relation C(v, v′ ) ∈ 2B to each pair (v, v′ ) of V × V . C is such that C(v, v) ⊆ {Id} and C(v, v′ ) = (C(v′ , v))-1 .

In what follows, given a QCN N = (V, C) and v, v′ ∈ V , N[v, v′ ] will denote the relation C(v, v′ ). N[v,v′ ]/r with r ∈ 2B is the QCN N ′ defined by N ′ [v, v′ ] = r, N ′ [v′ , v] = r-1 , and N ′ [v, v′ ] = N[v, v′ ] ∀(v, v′ ) ∈ (V × V ) \ {(v, v′ ), (v′ , v)}. Given a set of variables V , ⊥V will denote the particular QCN where each constraint is defined by the empty relation ∅. Given a QCN N = (V,C) we have the following definitions: N is said to be trivially inconsistent iff ∃v, v′ ∈ V with N[v, v′ ] = ∅. A solution of N is a mapping σ defined from V to the domain D such that for every pair (v, v′ ) of variables in V , (σ(v), σ(v′ )) satisfies N[v, v′ ], i.e., there exists a base relation b ∈ N[v, v′ ] such that (σ(v), σ(v′ )) ∈ b. N is consistent iff it admits a solution. Two QCNs are equivalent iff they admit the same solutions.

A sub-QCN N ′ of N, denoted by N ′ ⊆ N, is a QCN (V, C ′ ) such that N ′ [v, v′ ] ⊆ N[v, v′ ] ∀v, v′ ∈ V . An atomic QCN is a QCN where each constraint is defined by a base relation. A scenario S of N is an atomic consistent sub-QCN of N. A base relation b ∈ N[v, v′ ] with v, v′ ∈ V is feasible (resp. unfeasible) iff there exists (resp. there does not exist) a scenario S of N such that S[v, v′ ] = {b}. N is minimal iff ∀v, v′ ∈ V and ∀b ∈ N[v, v′ ], b is a feasible base relation of N. The unique equivalent minimal sub-QCN of N is denoted by Nmin. It is called the minimal QCN of N. N is ⋄-consistent or closed under weak composition iff ∀v, v′ , v′′ ∈ V , N[v, v′ ] ⊆ N[v, v′′ ] ⋄ N[v′′ , v′ ]. The closure under weak composition of N, denoted by ⋄(N), is the greatest ⋄-consistent sub-QCN of N .

Given two QCNs N = (V,C) and N ′ = (V,C ′ ), N ∪ N ′ denotes the QCN N ′′ = (V,C ′′ ) where N ′′ [v, v′ ] = N[v, v′ ] ∪N ′ [v, v′ ] for all v, v′ ∈ V . Given two QCNs N = (V, C) and N ′ = (V ′ , C′ ) such that N[v, v′ ] = N ′ [v, v′ ] for all v, v′ ∈ V ∩ V ′ , N ′ ⋓N denotes the QCN N ′′ = (V, C ′′ ) where N ′′ [v, v′ ] = N[v, v′ ] for all v, v′ ∈ V , N ′′ [v, v′ ] = N ′ [v, v′ ] for all v, v′ ∈ V ′ , and N ′′ [v, v′ ] = N ′′ [v′ , v] = B for all v ∈ V ′ \ V , v′ ∈ V \ V ′ .

In what follows, all considered graphs are undirected. Given two graphs G = (V, E) and G′ = (V ′ , E′ ), G is a subgraph of G′ , denoted by G ⊆ G′ , iff V ⊆ V ′ and E ⊆ E′ . A graph G = (V,E) is a chordal graph (some times also called triangulated graph) [Golumbic, 2004] iff each of its cycles of length strictly greater than 3 has a chord, i.e., an edge joining two vertices that are not adjacent in the cycle. KV with V a set of variables denotes the complete graph G = (V,E) where E = {(v, v′ ) : v, v′ ∈ V }. The constraint graph of a QCN N = (V,C) is the graph (V,E), denoted by G(N), for which we have that (v, v′ ) ∈ E iff N[v, v′ ] ̸= B. Given a QCN N = (V, C) and a graph G = (V,E), N is ⋄G-consistent [Chmeiss and Condotta, 2011] iff for ∀(v, v′ ), (v, v′′ ), (v, v′′ ) ∈ E we have that N[v, v′ ] ⊆ N [v, v′′ ] ⋄ N [v′′ , v′ ]. Given a QCN N ′ = (V, C), N ⊆G N ′ iff for each (v, v′ ) ∈ E we have that N[v, v′ ] ⊆ N ′ [v, v′ ].

A subclass of relations is a set A ⊆ 2B closed under converse, intersection, and weak composition. Given a relation r of 2B and a subclass A ⊆ 2B containing the universal relation (i.e., the relation B), A(r) denotes the smallest relation of A including r. Moreover, given a QCN N = (V,C), A(N) is the QCN N ′ = (V,C ′ ) defined by N ′ [v, v′ ] = A(N[v, v′ ]) ∀v, v′ ∈ V . In what follows, all the considered subclasses will contain the singleton relations of 2B .

Definition 2 Let A ⊆ 2B . We define properties (⋄⇒consistency) and (Patchwork⋄ ) as follows:

• A satisfies (⋄⇒consistency) iff for any not trivially inconsistent and ⋄-consistent QCN N , N is consistent.
• A satisfies (Patchwork⋄ ) iff for any not trivially inconsistent and ⋄-consistent QCNs N = (V, C) and N ′ = (V ′ , C′ ) with identical labeling of constraints on V ∩V ′ , QCN N ⋓N ′ is a consistent QCN.

We can notice that property (Patchwork⋄ ) is stronger than property (⋄⇒consistency). Moreover, property (Patchwork⋄ ) can be seen like a patchwork (or amalgamation) property restricted to ⋄-consistent QCNs. From [Huang, 2012], we can assert that subclasses HIA of IA and ˆH8, C8, and Q8 of RCC-8 satisfy (Patchwork⋄ ). From [Sioutis and Koubarakis, 2012], we have the following result:

Property 1 Let A ⊆ 2B be a subclass having property (Patchwork⋄ ), N = (V, C) a not trivially inconsistent QCN defined on A, and G = (V, E) a graph such that G(N) ⊆ G. If G is chordal and N is ⋄G-consistent then N is consistent.

3 Partial consistencies for QCNs

In this section we introduce and study a new form of partial consistency for QCNs, called ◆G-consistency, where G is a graph on the set of variables V of the considered QCN. Intuitively, a QCN N on V is ◆G-consistent iff for every pair of variables (v, v′ ) and every base relation b ∈ N [v, v′ ], after instantiating N [v, v′ ] with {b} and computing the closure under ⋄G-consistency, N[v, v′ ] is always defined by {b}. Formally, ◆G-consistency of a QCN is defined as follows:

Definition 3 Let N = (V,C) be a QCN and G = (V,E) a graph. N is said to be ◆G-consistent iff ∀v, v′ ∈ V and ∀b ∈ N [v, v′ ], {b} = ⋄G(N[v,v′ ]/{b})[v, v′ ].

If G is a complete graph, i.e., G = KV , we can easily verify that ◆G-consistency corresponds to ⋄B -consistency of the familly of ⋄f -consistencies studied in [Condotta and Lecoutre, 2010]. Interestingly, ◆G-consistency can be also seen as a partial singleton arc consistency (SAC) [Debruyne and Bessi`ere,

1997] for QCNs. Given a QCN N = (V, C) and a graph G = (V, E), for every b ∈ B and every v, v′ ∈ V , we will say that b is ◆G-consistent for N[v, v′ ] iff {b} = ⋄G(N[v,v′ ]/{b})[v, v′ ]. We have the following proposition:

Proposition 1 Let N = (V,C) and N ′ = (V,C ′ ) be two QCNs such that N ⊆ N ′ , and G = (V,E) a graph. For every b ∈ B and every v, v′ ∈ V , if b is ◆G-consistent for N[v, v′ ] then b is ◆G-consistent for N ′ [v, v′ ].

Next, we prove the following properties to show that there exists a closure under ◆G-consistency as with ⋄G-consistency:

Proposition 2 Let V be a set of variables and G = (V, E) a graph. We have: (1) for any QCNs N1 and N2 defined on V , if N1 and N2 are ◆G-consistent, then N1 ∪N2 is ◆G-consistent, and (2) every scenario S defined on V is a ◆G-consistent QCN.

Proof. (1) Let v, v′ ∈ V and b ∈ (N1 ∪ N2)[v, v′ ]. Suppose that N1 and N2 are ◆G-consistent. It is clear that b ∈ N1[v, v′ ] or b ∈ N2[v, v′ ]. Suppose that b ∈ N1[v, v′ ] (the other case is similar). Since N1 is ◆G-consistent, we have that b is ◆G-consistent for N1[v, v′ ]. Therefore, since N1 ⊆ N1 ∪N2, from Prop. 1 we have that b is ◆G-consistent for (N1 ∪ N2)[v, v′ ]. (2) Every scenario S defined on V is ⋄-consistent and, hence, ⋄G-consistent. Moreover, ∀v, v′ ∈ V and ∀b ∈ S[v, v′ ], S[v, v′ ] = {b}. Thus, ∀v, v′ ∈ V and b ∈ S[v, v′ ] we have that ⋄G(S[v,v′ ]/{b})[v, v′ ] = ⋄G(S)[v, v′ ] = S[v, v′ ] = {b}. ⊣

From this proposition we can assert that for a QCN N = (V,C) and a graph G = (V,E) there exists a unique largest ◆G-consistent sub-QCN of N, i.e., a closure of N under ◆G-consistency. By denoting this closure by ◆G(N), we have that ◆G(N) = {N ′ : N ′ ⊆ N and N ′ is ◆G-consistent}. Further, we have that ◆G(N) is equivalent to N since from Property (2) of the previous proposition we know that every scenario S of N is a ◆G(N) sub-QCN of N.

Function Make◆G(N ,G)

The naive algorithm corresponding to function Make◆G, allows computing ◆G(N) with a worst-case time complexity of O(α.|B|2 .|E|2 ) (where α is the worst-case time complexity for enforcing ⋄G-consistency). We can now obtain the following result:

Proposition 3 Let N = (V, C) be a QCN and G = (V, E) a graph. If N is ◆G-consistent then N is ⋄G-consistent.

Notice that in the general case a ⋄G-consistent QCN is not necessary ◆G-consistent. Now, we show that for QCNs defined on a subclass A having property (Patchwork⋄ ), enforcing ◆G-consistency using a chordal graph G(N) ⊆ G ensures the feasibility of the base relations belonging to the constraints of N corresponding to the edges of G.

Proposition 4 Let A ⊆ 2B be a subclass having property (Patchwork⋄ ), N = (V, C) a not trivially inconsistent QCN defined on A, and G = (V,E) a chordal graph such that G(N) ⊆ G. We have: (1) for every (v, v′ ) ∈ E and every b ∈ N[v, v′ ], b is ◆G-consistent for N[v, v′ ] iff b ∈ Nmin[v, v′ ], and (2) for every (v, v′ ) ∈ E, Nmin[v, v′ ] = ◆G(N)[v, v′ ].

Proof. (1) Consider a base relation b which is ◆G-consistent for N[v, v′ ] with (v, v′ ) ∈ E. Let N ′ be the QCN defined by N ′ = ⋄G(N[v,v′ ]/{b}). We can show that N ′ is not trivially inconsistent. Moreover, as N[v,v′ ]/{b} is defined on A, we know that N ′ is also defined on A. Consequently, from Property 1 we can assert that N ′ admits a scenario S. S is also a scenario of N since N ′ ⊆ N. Since N ′ [v, v′ ] = {b}, we can affirm that S[v, v′ ] = {b}. We can conclude that b ∈ Nmin[v, v′ ]. Now, consider b ∈ Nmin[v, v′ ] with (v, v′ ) ∈ E. There exists a scenario S of N such that S[v, v′ ] = {b}. From Prop. 2 we have that S is ◆G-consistent. Therefore, b is ◆G-consistent for S[v, v′ ]. From Prop. 1 we can conclude that b is ◆G-consistent for N[v, v′ ] because S ⊆ N. (2) can be established directly from (1) and the fact that ◆G(N) is an equivalent QCN of N for which every base relation b ∈ N[v, v′ ] with (v, v′ ) ∈ E is ◆G-consistent for (v, v′ ). ⊣

From this proposition we can notice that for a not trivially inconsistent QCN N on a subclass A having property (Patchwork⋄ ) and for a chordal graph G such that G(N) ⊆ G, we can compute ◆G(N ) by using function Make◆G whithout its outer loop (with a time complexity of O(α.|B|.|E|)).

Before considering the next result, note that given two QCNs N and N ′ defined on V and a graph G = (V,E), NG/N ′ denotes the QCN N ′′ = (V,C ′′ ) defined by N ′′ [v, v′ ] = N ′ [v, v′ ] if (v, v′ ) ∈ E, and N ′′ [v, v′ ] = N[v, v′ ] otherwise. We have the following result which will be useful in the sequel:

Proposition 5 Let N, N ′ , N ′′ be three QCNs defined on V , G a chordal graph, and A a subclass having property (Patchwork⋄ ) such that: G(N) ⊆ G, N ′ is an equivalent sub-QCN of N, and N ′′ is a not trivially inconsistent and ⋄G-consistent sub-QCN of N ′ with A(N ′′ ) ⊆G N ′ . By denoting N ′G/A(N ′′ ) by N ∗ , we have: (1) N ∗ is a consistent QCN, (2) each ◆G-consistent base relation of N ∗ [v, v′ ] with (v, v′ ) ∈ E is a feasible relation of N, and (3) each ◆KV -consistent base relation of N ∗ is a feasible relation of N .

Proof. (1) NG/N ∗ is clearly a not trivially inconsistent and ⋄G-consistent QCN defined on A such that G(NG/N ∗) ⊆ G. From Property 1 we know that NG/N ∗ is consistent and admits a scenario S, which is also a scenario of N ′G/N ∗. By remarking that N ′G/N ∗ and N ∗ are equal, we can affirm that S is scenario of N ∗ . (2) Consider a ◆G-consistent base relation b of N ∗ [v, v′ ] with (v, v′ ) ∈ E. As N ∗ ⊆ NG/N ∗, from Prop. 1 we have that b is a ◆G-consistent base relation of NG/N ∗[v, v′ ]. From Prop. 4, we can assert that b is a feasible base relation of NG/N ∗. Hence, b is also a feasible base relation of N since NG/N ∗ ⊆ N. (3) Each ◆KV -consistent base relation b of N ∗ is also a ◆KV -consistent base relation of N since N ∗ ⊆ N. From Prop. 4 (by considering KV as a chordal graph) we conclude that b is a feasible base relation of N . ⊣

4 Algorithm for the Minimal Labeling Problem

In order to solve the MLP, we present in this section algorithm Minimize. The embedded function Minimize has two parameters, the first one being a QCN N = (V, C) for which we aim to derive the feasible base relations, and the second one being a subclass A having property (Patchwork⋄ ). Minimize proceeds in an iterative manner that we explain as follows. In each iteration, a relation r is defined by a set of non treated base relations of a constraint N[v, v′ ], followed by the derivation of a consistent sub-QCN N ′′ of N defined on A, for which N ′′ [v, v′ ] contains some base relations of r and in particular feasible relations of N. In the case where such a sub-QCN does not exist, the base relations of r are non feasible. This process continues until all base relations of N are treated. The expected efficiency of function Minimize depends, on one hand, on the fact that several feasible (or unfeasible) base relations are derived in each iteration, and, on the other hand, on the fact that searching for the subQCNN ′′ and deriving feasible base relations can be made efficiently by applying partial consistencies ⋄G-consistency and ◆G-consistency for a given subclass A having property (Patchwork⋄ ), where G is a chordal graph such that G(N) ⊆ G.

Next, we consider the auxiliary function ⋄G -SubQCN. This function has three parameters: a QCN N = (V,C), a graph G = (V, E), and a subclass A ⊆ 2B . Note that this function is very similar to the ones proposed in [Chmeiss and Condotta, 2011; Sioutis and Koubarakis, 2012] for solving the consistency problem of a QCN. Function ⋄G -SubQCN aims to derive and return a not trivially inconsistent and ⋄G-consistent QCN N ′ , such that N ′ ⊆ N, A(N ′ ) ⊆G N, and ∀(v, v′ ) ̸∈ E, N ′ [v, v′ ] = N[v, v′ ]. We remind the reader that A contains the singleton relations. In the case where such a QCN N ′ does not exist, the function returns ⊥V . For this purpose, a backtrack search is realized by performing the closure under ⋄G-consistency for propagating constraints and ensuring that the result is ⋄G-consistent. In each step, a constraint corresponding to an edge of G is selected and split into non-empty relations of A. Then, this constraint is iteratively instantiated with each of these relations. The search continues by recursive calls of ⋄G -SubQCN. We have the following result:

Proposition 6 Let N = (V,C) be a QCN, G = (V,E) a graph, and A ⊆ 2B a subclass. If N is consistent, then function ⋄G -SubQCN with N, G, A as parameters returns a not trivially inconsistent and ⋄G-consistent QCNN ′ , such that A(N ′ ) ⊆G N and ∀(v, v′ ) ̸∈ E, N ′ [v, v′ ] = N[v, v′ ].

Proof. If N is consistent then N has a scenario S. Consider the QCN N S = (V,C S ) defined by N S [v, v′ ] = S[v, v′ ], if (v, v′ ) ∈ E, and N S [v, v′ ] = N[v, v′ ], otherwise. N S is ⋄G-consistent and, during a complete search, a QCN N ′ such

Function Minimize(N ,A)

Function ⋄G -SubQCN(N ,G,A)

in : A QCN N=(V, C), a graph G=(V, E), a subclass A. output : A ⋄G-consistent sub-QCNN ′ with A(N ′ ) ⊆G N. 1 begin 2 N ′ ← ⋄G(N); 3 if N ′ [v, v′ ] = ∅ for some (v, v′ ) ∈ E then return ⊥V ; 4 Select (v, v′ ) ∈ V ×V s.t. A(N ′ [v, v′ ]) ̸⊆N[v, v′ ]; 5 if such a pair does not exist then return N ′ ; 6 Split N ′ [v, v′ ] into sub-relations r1, . . . , rk ∈ A (k < |B|); 7 N ′′ ←N ′ ; 8 foreach i ∈ 1, . . . , k do 9 N ′ [v, v′ ] ← ri; N ′ [v′ , v] ← r-1 i ; 10 N ′ ← ⋄G-SubQCN(N ′ ,G,A); 11 if N ′ ̸= ⊥V then return N ′ ; ; 12 N ′ ←N ′′ ; 13 return ⊥V

that N S ⊆G N ′ will be considered. As ⋄G(N ′ ) is not trivially inconsistent and ⋄G-consistent, it will be returned at the end. ⊣

Function Minimize uses also an auxiliary function called extractFeasible taking as parameters two QCNs N and N ′ ,

Function extractFeasible(N ,N ′ ,G)

defined on V and a graph G = (V, E). This function returns N ′ augmented with ◆G-consistent base relations b belonging to N[v, v′ ] with (v, v′ ) ∈ E, and ◆KV -consistent base relations b belonging to N[v, v′ ] with (v, v′ ) ̸∈ E.

Now, we describe in detail function Minimize. Minimize takes as parameters a QCN N = (V, C), for which we want to calculate the feasible base relations, and a subclass A ⊆ 2B having property (Patchwork⋄ ). To begin with, Minimize comprises the following four successive steps: the initialization of different variables, the calculation of the feasible base relations corresponding to the edges E of a chordal graph, the minimization step by considering the constraints not corresponding to E, and finally, the return of the result.

The different variables initialized during the first step are: NI, N ∗ , and G. NI allows saving the initial state of QCN N given as parameter. QCN N ∗ accumulates the base relations of N detected as feasible during the treatment and is initialized to ⊥V . At the end of the treatment, N ∗ will be the minimal QCN of NI. G is initialized by a chordal graph of G(N). An optional preliminary treatment is performed (line 3) by calculating the closure under ⋄-consistency of N. Its aim is to quickly eliminate some unfeasible base relations. We note here that during this process, and until the end of the treatment, N is an equivalent sub-QCN of NI . Only unfeasible base relations will be removed from N.

In the second step (line 5), the constraints of NI corresponding to the set of edges E are treated until all base relations of these constraints are detected as feasible and accumulated into N ∗ , or as unfeasible and removed fromN. For this purpose, a pair (v, v′ ) ∈ E such that N[v, v′ ] contains some non marked feasible base relations is selected in line 6. These base relations correspond to relation r (line 7). In line 8, a QCN N ′ is computed from function ⋄G -SubQCN with N[v, v′ ]/r, G, and A as parameters. Two cases must be considered: N ′ = ⊥V , and N ′ ̸= ⊥V . For N ′ = ⊥V , we can affirm from Proposition 6 that N [v, v′ ]/r is inconsistent, and, therefore, the base relations of r are unfeasible for N and also for NI, since they are equivalent. The base relations of r can be removed fromN (line 10). Now, suppose that N ′ ̸= ⊥V . In line 12, QCN NG/A(N ′ ) is saved into N ′′ . From Proposition 5 we know that each ◆G-consistent base relation of N ′′ [v′′ , v′′′ ] with (v′′ , v′′′ ) ∈ E and each ◆KV -consistent base relation of N ′′ [v′′ , v′′′ ] with (v′′ , v′′′ ) ̸∈ E are feasible relations of NI and can be added to N ∗ (line 13). Notice that since N ′′ is consistent, at least one new detected feasible base relation b ∈ r is added to N ∗ [v, v′ ]. Following the second step, all base relations of NI[v, v′ ] with (v, v′ ) ∈ E have been treated. The third step of Minimize finishes the minimization of NI by considering the constraints NI[v, v′ ] with (v, v′ ) ̸∈ E. Notice that some base relations of these constraints have been already detected as feasible at step 2. Due to space constraints, and as Step 3 is very similar to Step 2, we are not going to describe it in details. Following the third step we can then affirm that N ∗ , returned in line 24, corresponds to the minimal QCN of NI. Thus, we can establish the following main result:

Theorem 1 Given a QCN N = (V, C) and a subclass A ⊆ 2B having property (Patchwork⋄ ), function Minimize, with N and A as parameters, returns Nmin.

Corollary 1 Function Minimize with N a QCN of IA (resp. of RCC-8) and A = HIA (resp. A ∈ ˆH8, C8, andQ8) as parameters returns Nmin.

5 Experiments

In order to study the behavior of algorithm Minimize, we conducted experiments with QCNs of IA and RCC-8. These QCNs were generated using model S [Nebel, 1996]. This model can randomly generate consistent QCNs according to three parameters, n, d, and s, where n is the number of variables of the generated QCNs, d is the average number of variables connected with non trivial constraints (constraints defined by a relation other than B), and s is the average number of base relations of a non trivial constraint. For this model, the consistency of a generated QCN is guaranteed by augmenting it with a consistent scenario. A set of QCNs generated according to model S using parameters n, d, and s will be denoted by S(n, d, s). We present experiments with instances issued from series S(n, d, |B|/2), with n varying between 30 and 60 with an incremental step of 10, and d varying between 4 and 22 with an incremental step of 0.5. For each series, we generated 50 QCNs. The subclasses of relations used as parameters for function Minimize are the two maximal tractable subclasses HIA for IA and ˆH8 for RCC-8. A timeout of 5 hours was given for each series.

In short, a (linear) technique used to triangulate a graph consists of adding extra edges produced by eliminating vertices one by one. Many heuristics have been proposed to order the vertices, here we use the GreedyFillIn (GFI) heuristic [Bodlaender and Koster, 2010] to triangulate the constraint graph of a QCN (line 3 of the function Minimize) and obtain a chordal graph. In what follows, MinimizeGFI denotes the function Minimize with use of GFI triangulation, whereas MinimizeKV denotes the function Minimize where the chordal graph used is the complete graph KV .

Further, NaiveMin refers to a naive minimization algorithm. NaiveMin, after calculating the closure under ⋄- consistency to quickly prune some unfeasible base relations, continues with the following steps for each constraint and each base relation it comprises: (1) it instantiates the constraint with the considered base relation, (2) then, it checks the feasibility of this base relation by checking the consistency of the obtained QCN using some maximal tractable subset of relations (for our experiments subclasses HIA or ˆH8 and the complete graph KV are used as parameters for function ⋄G -SubQCN).

For every series, we note that the general approach used by Minimize greatly performs the naive approach followed by NaiveMin. As an example, consider Figure 3 which illustrates the CPU time required by the three functions to solve the series S(40, d, 6.5) and S(50, d, 6.5) of IA. Note that for n > 50, function NaiveMin cannot solve the series of IA in the 5 hours given timeout. Further, by comparing the CPU time required by MinimizeKV and MinimizeGFI, the latter has better performance. Using judicious triangulation with GFI heuristics, increases the efficiency of detecting the feasibility or the unfeasibility of the base relations belonging to a constraint associated with an edge of the graph issued by the triangulation (in Step 2 of Minimize). Similar results were obtained for RCC-8 that we omit to present here due to space constraints.

6 Conclusions

In this paper we introduced a new algorithm called Minimize to solve the minimal labeling problem of QCNs that considers tractable subclasses, for which ⋄-consistent QCNs have property (Patchwork⋄ ), and chordal constraint graphs. Further, this algorithm applies partial consistencies ⋄G-consistency and ◆G-consistency on the chordal graph G, to efficiently derive feasible or unfeasible base relations. Future work consists of using other methods of triangulation and comparing the behavior of our algorithm for these different methods. Another research perspective consists of defining specific algorithms for the MLP using subclasses having other properties than the (Patchwork⋄ ) property considered here.