Consistency and Set Intersection

1 Introduction

A fundamental problem in Constraint Networks is to study properties of consistency in some networks with particu­ lar constraints or structure. There have been two main ap­ proaches to this problem.

The first is to utilise topological structure of the network. For example, where the network forms a tree structure, arc consistency is sufficient to make the network globally consis­ tent [Freuder, 1982].

Another approach is to make use of semantic properties of the constraints. For monotone constraints, path consis­ tency implies global consistency [Montanari, 1974]. Dechter [1992] shows that a certain level of consistency in a net­ work whose domains are of limited size ensures global con­ sistency. VanBeek and Dechter [1995] generalize monotone constraints to a larger class of row convex constraints. Later, they [1997] study the consistency inside a network with tight and loose constraints.

In this paper, we present a new framework 1 which unifies well known results mainly along the second approach (includ­ ing [van Beek and Dechter, 1995; 1997]). The power of this framework is that it allows the study of the relationship be­ tween local and global consistency from the perspective of set intersection.

For example, one property of set intersection is that if ev­ ery pair (2) of tree convex sets intersect, the whole collection of these sets also intersect. The main point is that local in­ formation on intersection of every pair of sets gives global information on intersection of all sets. Intuitively, this can be related to getting global consistency from local consistency. Our framework enables us to lift the result on tree convex sets to the following result on consistency. For a binary net­ work of tree convex constraints, (2+ I )-consistency (path con­ sistency) implies global consistency.

Properties of the intersection of tree convex sets, small sets, large sets are presented in section 3. Section 4 develops the framework which consists of a lifting lemma together with a proof schema which gives a generic way of using the lift­ ing lemma to get consistency results from properties of set intersection. One benefit of the framework lies in that it pro­ vides a modular way to greatly simplify the understanding and proof of results on consistency. This benefit is consid­ erable as often the proof of many existing results is complex and "hard-wired".

We demonstrate the power of the framework by showing three new consistency results as well as a number of well known results. The first is a generalization of global consis­ tency of row convex constraints to a network of tree convex constraints which is presented in section 5. The second is a new result on global consistency on weakly tight networks in section 6. These networks only require certain constraints to be m-tight rather than all constraints as shown in [van Beek and Dechter, 1997]. The final result is presented in section 8. This is most interesting because we can make certain net­ works globally consistent by enforcing relational consistency, but this may not be achievable in previous work (for example [van Beek and Dechter, 1997]).

1 Our work can be related to the first approach in those cases where the network topology leads to some set intersection property.

2 Preliminaries

A constraint network R is defined as a set of variables N = {x1,x2, · · · ,xn}; a set of finite domains D = {D1, D2, · · ·, Dn} where domain Di, for all i E l..n, is a set of values that variable Xi can take; and a set of constraints C = { csll cs2, · · · , csJ where Si, for all i E 1.. n, is a subset of { x1, x2, · · · , Xn} and each constraint cs; is a relation de­ fined on domains of all variables in Si . The arity of constraint CS; is the number of variables in Si .

An instantiation of variables Y = { x1, · · ·, Xj} is denoted by a = (a1, · · · ,aj) where ai E Di fori E l..j. An ex­ tension of a to a variable x( ¢. Y) is denoted by (a, u) where u E Dx . An instantiation of a set of variables Y is consis­ tent if it satisfies all constraints inn which don't involve any variable outside Y.

A constraint network Risk-consistent if and only if for any consistent instantiation a of any distinct k - 1 variables, and for any new variable x, there exists u E Dx such that (a, u) is a consistent instantiation of the k variables. n is strongly k-consistent if and only if it is j-consistent for all j ~ k. A strongly n-consistent network is called globally consistent.

3 Properties on Set Intersection

The set intersection property which we are concerned with is:

Given a collection of l finite sets, under what con­ ditions is the intersection of alll sets not empty?

We useS to denote the collection of l sets: { E1, E2, · · · , Ez}, and U the union of all the sets inS, that is U = U Ei. iEl .. l

This property may not make sense for collections of arbi­ trary sets. Here, we study sets with two restrictions.

3.1 Sets with Convexity Restrictions

Definition 1 Given a set U and a tree T with vertices U. A set A ~ U is tree convex iff there exists a subtree, with only vertices A, ofT. The sets inS are tree convex if there is a tree on U under which every set in S is tree convex.

'

Figure I: A tree with nodes a, b, c, d, e

Example. Consider a set U = {a, b, c, d, e} and a tree in Fig I . The subset {a, b, c, d} is tree convex. So is the set {b, a, c, e} since the elements in the set consists of a subtree. However, {b, c, e} is not tree convex for they does not form a subtree of the given tree.

Consider X = { {1, 9}, {3, 9}, {5, 9} }. A tree can be con­ structed on {1, 3, 5, 9} with 9 being the root and 1, 3, 5 being its children. Each set in X covers the nodes of exactly one branch of the tree. Hence the sets in X are tree convex. D

Tree convex sets have the following intersection property.

Lemma 1 (Tree convex Sets Intersection) Assume the sets inS are tree convex. n Ei =f. 0 iff for every Ei , Ej E S. iEl..l

Proof. Let T be a tree such that there exists a subtree Ti for each Ei E S. We can regard T as a rooted tree and thus every Ti (i E l..Z) can be regarded as a rooted tree whose root is exactly the node nearest to the root ofT. Let ri denote the root of Ti fori E l..Z.

the trees {Ti I i E l..Z} is not empty. The following proposi­ tion on subtrees, whose proof is omitted, is necessary in our main proof.

To prove n Ei =f. 0, we want to show the intersection of iEl..l

Proposition 1 Let the root ofT be r. Given two sub­ trees T1 and T2 ofT with roots r 1 and r2 respectively. Let r1 be not closer to r than r2, and T the intersection ofTl and T2. r 1 is the root ofT ifT is not empty.

LetT= n Ti. We are ready now to prove our main result iEl..l

T =f. 0. We select a tree T max from T1, T2, · · · , Tz such that its root r max is the farthest away from r of T among the roots of the concerned trees. In terms of proposition I, that T max intersect with every other trees implies that rmax is a node of every Ti (i E l..Z). Therefore, rmax E T . D

Tree convexity on a collection of sets imposes a strong re­ striction on the relationship among these sets in the sense that each set forms part of a tree. If the tree is a chain, it can be thought of as a total order on the elements of all the sets. This leads to the notion of convex sets upon which the well-known row-convex constraints are defined.

Definition 2 Given a set U and a total ordering "::S" on it, a set A C U is convex if the elements in it are consecutive under the ordering, that is

Given S and U, the sets in S are convex if there is a total ordering on U such that every set in S is convex under the ordering.

Example. The set of real numbers between I and 2 is con­ vex under the usual ordering of numbers. {1, 9} and {3, 9} are convex with a total ordering 1 ::S 9 ::S 3. However, {1, 9}, {3, 9} and {5, 9} are not convex under any total or­ dering on {1, 3, 5, 9}. D

The following result on convex sets, a set-based version of van Beek and Dechter's [1995, lemma 3.1], is immediate.

Corollary 1 (Convex Sets Intersection) Assume the sets in S are convex under a total ordering on U. n Ei =f. 0 iff for iEl..l

3.2 Sets with Cardinality Restrictions

The following results are on arbitrary sets where the only re­ striction is on the size of sets.

Lemma 2 (Small Set Intersection) Given a collection of sets S. Assume there is a set E E S such that lEI ~ m.

iff the intersection of any m + 1 sets from S is not empty.

Proof. The necessary condition is immediate.

The sufficient condition is proven by induction on l. It is obviously true when l ::; m + 1. Assuming that k (> m) sets intersect, we show that any k + 1 sets intersect. Without loss of generality, the subscripts of the k + 1 sets are numbered from 1 to k + 1 and let IE1 1 ::; m. Let A be the intersection of all the k + 1 sets except E;:

A;= E1n· · -nE;-1nEi+1n· · -nEk+I, for 1 < i::; k+l. If A; n A1 =f. 0 for some i,j E 2 .. k + 1, i =f. j,

Assume the contrary that A; n A1 = 0 for all distinct i and j. According to the construction of A; 's,

and lA; I ~ 1 by the induction assumption. Henceforth,

which contradicts IE1I ::; m. D

We have an immediate corollary of the lemma when all sets of concern have at most m elements.

Corollary 2 (Small Sets Intersection) For any E; E S, as­ sume E; is finite and IE; I ::; m ( < l) . n E; =f. 0 iff the iEl..!

intersection of any m + 1 sets from S is not empty.

Another special case is that some set has only one element.

Corollary 3 (Singleton Set Intersection) Given a collec­ tion of sets S. Assume there is a set E E S such that lEI = 1. n E; =f. 0 iff all sets mutually intersect. iEl..!

Motivated by [van Beek and Dechter, 1997, lemma 4.1 in page 561 ], we consider the intersection of sets, each of which has at least some number of elements.

Lemma 3 (Large Sets Intersection) For all E; E S, as­ sume E; is finite and IE; I ~ m . Let I U E;l = d. if iEl..!

Proof. Let U = U E;, and A; = U- E; for all i ::; l. It iEl..! is immediate that U A;~ U.

We know

For lA; I ::; d- m , we have

Hence, U A; is a proper subset of U. There exists x E U iEl..! such that x ¢:. A; for all i ::; l, which implies that x E E; for all i ::; l. D

4 Set Intersection and Consistency

In this section we relate set intersection with consistency in constraint networks.

Underlying the concept of consistency is whether an in­ stantiation of some variables can be extended to a new vari­ able such that all relevant constraints to the new variable are satisfied. A relevant constraint to a variable x ; is a constraint where only x; is uninstantiated and the others are instanti­ ated. Each relevant constraint allows a set (possibly empty) of values for the new variable. This set is called extension set below. The satisfiability of all relevant constraints depends on whether the intersection of their extension sets is non-empty (see lemma 4).

Definition 3 Given a constraint cs,. a variable x E 5; and any instantiation a of 5; - { x }, the extension set of a to x with respect to cs, is defined as

An extension set is trivial if it is empty; otherwise it is non­ trivial.

Throughout this paper, it is often the case that an instantia­ tion a of 5- { x} is already given where 5- { x} is a superset of 5; - { x}. Let b be the instantiation obtained by restricting a to the variables only in 5; - { x}. For ease _of presentation, we continue to use E;,x (a), rather than E;,x (b), to denote the extension of b to x under constraint cs,. Where the context is clear, we may omit some of the three parameters i, a and x.

Example. Consider the network with variables {X, X1, X2, X4, X5}:

Let a = (a, b, a) be an instantiation of variables Y { X1, x2, x4 }. The relevant constraints to x are cs, cs 2 , and cs 3 · cs 4 is not relevant since it has two uninstantiated vari­ ables. The extension sets of a to x with respect to the relevant constraints are:

The intersection of the above extension sets is not empty, im­ plying that a can be extended to satisfy all relevant constraints cs 1 , cs 2 and cs 3 ·

Leta= (b,b) bean instantiation of {xz,x}. E1,x 1 (a) = 0 and it is trivial. In other words, when an instantiation has a trivial extension set, it can not be extended to satisfy the constraint of concern. D

The relati011ship between k-consistency and set intersection is characterized by the following lemma which is a direct con­ sequence of the definition of k-consistency.

Lemma 4 (Set Intersection and Consistency; lifting) A constraint network n is k-consistent if and only if for any consistent instantiation a of any ( k - 1) distinct variables Y = {x1, X2, · · ·, Xk-d. and any new variable Xk,

where Eii is the extension set ofii to Xk with respect to cs, .. J and cs,, , · · · , cs, 1 are all relevant constraints.

The insight behind this lemma is to see consistency from the perspective of set intersection.

Example. Consider again the previous example. We would like to check whether the network is 4-consistent. Con­ sider the instantiation ii of Y again. This is a trivial consis­ tent instantiation since the network doesn't have a constraint among the variables in Y . To extend it to x, we need to check the first three constraints. The extension is feasible because the intersection of E1 , E2, and E3 is not empty. We show the network is 4-consistent, by exhausting all consistent in­ stantiations of any three variables. Conversely, if we know the network is 4-consistent, we can immediately say that the intersection of the three extension sets of ii to x is not empty. 0

The usefulness of this lemma is that it allows consistency information to be obtained from the intersection of extension sets, and vice versa. Using this view of consistency as set in­ tersection, some results on set intersection properties, includ­ ing all those in section 3, can be lifted to get various consis­ tency results for a constraint network through the following proof schema.

Proof Schema

1. (Consistency to Set) From a certain level of consistency in the constraint network, we derive information on the intersection of the extension sets according to lemma 4.
2. (Set to Set) From the local intersection information of sets, information may be obtained on intersection of more sets.
3. (Set to Consistency) From the new information on in­ tersection of extension sets, higher level of consistency is obtained according to lemma 4.
4. (Formulate conclusion on the consistency of the con­ straint network). 0

Given the proof schema, lemma 4 is also called the lifting lemma.

In the following sections, we demonstrate how the set in­ tersection properties and the proof schema are used to obtain new and also well known results on consistency of a network.

5 Application 1: Global Consistency of Tree Convex Constraints

The notion of extension set plays the role of a bridge between the restrictions to set(s) and properties of special constraints. The sets in lemma 1 are restricted to be tree convex. If all extension sets of a constraint is tree convex, we caB this constraint tree convex. ..

Definition 4 A constraint cs is tree convex with respect to x if and only if the sets in

are tree convex. cs is tree convex if it is tree convex wrt every x E S under a common tree on the union of domains involved.

{(1, 1),(1,9),(3,3),(3,9),(5,5),(5,9),(9,1),(9,9)} is an example of a tree convex constraint but it is not row convex.

Definition 5 A constraint network is tree convex if and only if all constraints are tree convex under a common tree on the union of all domains.

Convex sets naturally give rise to convex constraints which is a special case of tree convex constraints.

Definition 6 A constraint cs is row convex with respect to x if and only if the sets in

are convex. It is row convex if under a total ordering on the union of involved domains, it is row convex wrt every x E S. A constraint network is row convex iff all constraints are row convex under a common total ordering on the union of all domains.

The consistency results on these networks can be derived from the property of set intersection using the proof schema. We obtain the main result of this section.

Theorem 1 (tree convexity) Let R be a network of con­ straints with arity at most r and R be strongly 2( r - 1) + 1 consistent. !JR is tree convex then it is globally consistent.

Proof. The network is strongly 2(r - 1) + 1 consistent by assumption. We prove by induction that the network is k consistent for any k E { 2r, · .. , n}.

Consider any instantiation ii of any k- 1 variables and any new variable x. Let the number of relevant constraints be l . For each relevant constraint there is one extension set of ii to x. So we have l extension sets. If the intersection of alll sets is not empty, we have a value for x such that the extended instantiation satisfies all relevant constraints.

(Consistency to Set) Consider any two of the l extension sets: E1 and E2 · The two corresponding constraints involve at most 2(r -1) + 1 variables since the arity of a constraint is at most r and each of the two constraints has x as a variable. According to the consistency lemma, that R is 2(r- 1) + !­ consistent implies that the intersection of E1 and E2 is not empty.

(Set to Set) Since all relevant constraints are tree convex under the given tree, the extension sets of ii to x are tree con­ vex. Henceforth, the fact that every two of the extension sets intersect shows that the intersection of all l extension sets is not empty, in terms of the tree convex sets intersection lemma.

(Set to Consistency) From the consistency lemma, we have that Risk-consistent. o

Since a row convex constraint is tree convex, we have the following result.

Corollary 4 (row convexity) [van Beek and Dechter, 1995] Let R be a network of constraints with arity at most r and R be strongly 2( r- 1) + 1 consistent. If there exists an ordering of the domains D1 , · · · , Dn ofR such that R is row convex, R is globally consistent.

This can also be proved directly by lifting corollary 1.

6 Application II: Global Consistency on Weakly Tight Networks

In this section, we study networks with some tight constraints. The m-tight property of a constraint is related to the cardinal­ ity of the extension set in the following way.

Definition 7 A constraint cs, is m-tight with respect to x E S; iff for any instantiation a of S; - { x },

A constraint cs, ism-tight iff it is m-tight with respect to every XES;.

Definition 8 A constraint network is weakly m-tight at level k iff f or every set of variables { x1 , · · · , Xi}( k ~ l ~ n) and a new variable, there exists an m-tight constraint in the rele­ vant constraints after the instantiation of the l variables.

The small set intersection lemma gives the following theo­ rem.

Theorem 2 (Weak Tightness) If a constraint network R with constraints of arity at most r is strongly ( ( m + 1) ( r- 1) + 1 )­ consistent and weakly m-tight at level ( ( m + 1) ( r - 1) + 1 ), it is globally consistent.

The proof is similar to the theorem on tree convexity.

Immediately we have the following result which is a main result in [ vart Beek and Dechter, 1997].

Corollary 5 (Tightness) [van Beek and Dechter, 1997] If a constraint network R with constraints that are m-tight and of arity at most r is strongly ( ( m + 1) ( r - 1) + 1 )-consistent, then it is globally consistent.

This result can of course be directly lifted from corollary 2. Corollary 5 requires every constraint to be m-tight. The weak tightness theorem on the other hand does not require all con­ straints to be m-tight. The following example illustrates this difference.

Example. For a weakly m-tight network, we are inter­ ested in its topological structure. Thus we have omitted the domains of variables here. Consider a network with five vari­ ables labelled {1 , 2, 3, 4, 5}. In this network, for any pair of variables and for any three variables, there is a constraint. As­ sume the network is already strongly 4-consistent.

Since the network is already strongly 4-consistent, we can simply ignore the instantiations with less than 4 variables. This is why we introduce the level at which the network is weakly m-tight. The interesting level here is 4. Table 1 shows the relevant constraints for each possible extension of four instantiated variables to the other one. In the first row, 1234 --+ 5 stands for extending the instantiation of variables {1 , 2, 3, 4} to variable 5. Entries in its second column denote a constraint. For example, 125 denotes c125 . If the constraints on {1, 2, 5} and {1, 3, 4} (suffixed by* in the table) are m­ tight, the network is weakly m-tight at level 4. Alternatively, if the constraints {1 , 5}, {2, 3} and {3, 4} (suffixed by+) are m-tight, the network will also be weakly m-tight. However, the tightness corollary requires all binary and ternary con­ straints to be m-tight. The weak m-tightness theorem needs significantly less constraints to be m-tight. Further results are in section 8. D

7 Application III: Constraint Looseness

To make the presentation complete, we list the result on looseness of constraints by van Beek and Dechter [1997] (see also [Zhang and Yap, 2003]) as an instance of our framework.

The m-loose property of a constraint is related to the cardi­ nality of extension set in the following way.

Definition 9 A constraint cs , ism-loose with respect to x E S; iff for any instantiation a of S; - { x }, JE;,x I ;::=: m . A constraint cs, ism-loose iff it ism-loose with respect to every XE S; .

The large set intersection lemma is lifted to the following result on constraint looseness.

Theorem 3 (Looseness) Given a constraint network with domains that are of size at most d and constraints that are m­ loose and of arity at least r, r ;::=: 2. It is strongly k-consistent, where k is the maximum value such that binomial(k -1, r1) ~ fd/ (d- m)l- 1.

8 Application IV: Making Weakly Tight Networks Globally Consistent

In this section, relational consistency will be used to make a constraint network globally consistent.

Definition 10 [van Beek and Dechter, 1997] A constraint network is relationally m-consistent iff given (1) any m dis­ tinct constraints cs, , · · · , cs"'. and (2) any x E n~1 S;, and (3) any consistent instantiation a of the variables in (U~1 S; - { x} ). there exists an extension of a to x such that the extension is consistent with the m relations. A net­ work is strongly relationally m-consistent if it is relationally j-consistentfor every j ~ m .

All the results on small set intersection and tree convex set intersection in section 3 can be rephrased by using relational consistency. For example, a new version of weak tightness is shown below. Its proof can be easily obtained following the proof schema.

Theorem 4 (Weak Tightness) If a constraint network R of constraints with arity of at most r is strongly relationally (m+ !)-consistent and weakly m-tight at level of(m+ l)(r1) + 1, it is globally consistent.

Consider the weak m-tightness theorem 2 in section 6 based on local k-consistency. A weakly m-tight network in general may not have the level of consistency required by the theorem. To obtain global consistency, one may try to en­ force this level of consistency. However, this may result in new constraints with higher arity in the network. The new constraints may in tum require a higher level of consistency to ensure global consistency. Therefore it is difficult to pre­ dict an exact level of consistency to enforce on the network to make it globally consistent.

Using relational consistency, it is possible to obtain global consistency by enforcing local consistency on the network. In order to achieve our main result we need a stronger version of m-tightness -proper m-tightness.

Definition 11 A constraint cs; is properly m-tight with re­ spect to X E Si iff for any instantiation ii of Si - {X},

A constraint cs; is properly m-tight iff it is properly m-tight with respect to every x E Si .

A constraint is m-tight if it is properly m-tight. The con­ verse may not be true.

A weakly properly m-tight network is defined by replacing "m-tight" with "properly m-tight" in definition 8 (section 6).

We have the following observation on the weak m­ tightness and weak proper m-tightness of a network.

Proposition 2 A constraint network is weakly m-tight and weakly properly m-tight respectively if the constraint between every two variables in the network is m-tight and properly m-tight respectively.

It is easy to verify that the proper m-tightness of the binary constraints is preserved during the procedure to enforce cer­ tain level of consistency in the network. So we have the main result of this section.

Theorem 5 (Weak Proper-Tightness) Given a constraint net­ work whose constraint on every two variables is properly m­ tight. It is globally consistent after it is made relationally m + 1-consistent.

This theorem follows immediately from the discussion above and theorem 4. The implication of this theorem is that as long as we have certain properly m-tight constraints on certain combinations of variables, the network can be made globally consistent by enforcing relational m+ 1-consistency.

9 Summary

We demonstrate how to infer properties of consistency on a network purely by making use of set intersection properties. In addition to the results shown here, some other results can also be obtained by the lifting lemma. For example, the work of David [1993] can be obtained by lifting the singleton set corollary 3. The work of Faltings and Sam-Haroud [1996] is on convex constraint networks in continuous domains and the idea there is to lift Helly's theorem on intersection of convex sets in Euclidean spaces.

We show a number of new consistency results which we believe are significant progress to convexity and tightness of constraints since van Beek and Dechter's work [1995; 1997]. We identify a class of tree convex constraints which is a superset of row convex constraints [van Beek and Dechter, 1995]. In a network of tree convex constraints, global consis­ tency is ensured by a certain level of local consistency.

We show that in a network of arbitrary constraints, local consistency implies global consistency whenever there are m­ tight constraints on certain variables (e.g. theorem 2). How­ ever, when the network does not have the required local con­ sistency, global consistency may not be simply obtained by enforcing such level of local consistency. A surprising re­ sult is that as long as the constraint between every pair of variables is properly m-tight in an arbitrary network, global consistency can be achieved by enforcing a certain level of relational consistency ( theorem 5). In previous work (e.g. [van Beek and Dechter, 1997]), all constraints are required to be m-tight which may be violated by newly introduced constraints in the process of enforcing the intended relational consistency.

A promising line of work is to find more properties under which a network is weakly properly m-tight. Another obvi­ ous direction is to find other classes of sets with intersection properties which will likely give useful consistency results.