Constraint tightness and looseness versus local and global consistency.
Constraint networks are a simple representation and reasoning framework with diverse applications. In this paper, we identify two new complementary properties on the restrictiveness of the constraints in a networkconstraint tightness and constraint loosenessand we show their usefulness for estimating the level of local consistency needed to ensure global consistency, and for estimating the level of local consistency present in a network. In particular, we present a sufficient condition, based on constraint tightness and the level of local consistency, that guarantees that a solution can be found in a backtrack-free manner. The condition can be useful in applications where a knowledge base will be queried over and over and the  preprocessing costs can be amortized over many queries. We also present a sufficient condition for local consistency, based on constraint looseness, that is straightforward and inexpensive to determine. The condition can be used to estimate the level of local consistency of a network. This in turn can be used in deciding whether it would be useful to preprocess the network before a backtracking search, and in deciding which local consistency conditions, if any, still need to be enforced if we want to ensure that a solution can be found in a backtrack-free manner. Two definitions of local consistency are employed in characterizing the conditions: the traditional variable-based notion and a recently introduced definition of local consistency called relational  consistency.
Introduction
Constraint networks are a simple representation and reasoning framework. A
problem is represented as a set of variables, a domain of values for each variable,
and a set of constraints between the variables. A central reasoning task is then
to find an instantiation of the variables that satisfies the constraints. In spite of
the simplicity of the framework, many interesting problems can be formulated as
constraint networks, including graph coloring, scene labeling, natural language
parsing, and temporal reasoning.
In general, what makes constraint networks hard to solve is that they can
contain many local inconsistencies. A local inconsistency is an instantiation
of some of the variables that satisfies the relevant constraints that cannot be
extended to an additional variable and so cannot be part of any global solution.
If we are using a backtracking search to find a solution, such an inconsistency
can lead to a dead end in the search. This insight has led to the definition of
conditions that characterize the level of local consistency of a network [12, 18, 21]
and to the development of algorithms for enforcing local consistency conditions
by removing local inconsistencies (e.g., [2, 7, 10, 18, 21]).
Local consistency has proven to be an important concept in the theory and
practice of constraint networks for primarily two reasons. First, a common
method for finding solutions to a constraint network is to first preprocess the
network by enforcing local consistency conditions, and then perform a back-tracking
search. The preprocessing step can reduce the number of dead ends
reached by the backtracking algorithm in the search for a solution. With a
similar aim, local consistency techniques can be interleaved with backtracking
search. The effectiveness of using local consistency techniques in these two ways
has been studied empirically (e.g., [4, 6, 13, 14, 23]). Second, much previous
work has identified conditions for when a certain level of local consistency is
sufficient to guarantee that a network is globally consistent or that a solution
can be found in a backtrack-free manner (e.g., [5, 7, 11, 12, 21, 29]).
In this paper, we identify two new complementary properties on the restrictiveness
of the constraints in a network-constraint tightness and constraint
looseness-and we show their usefulness for estimating the level of local consistency
needed to ensure global consistency, and for estimating the level of local
consistency present in a network. In particular, we present the following results.
We show that, in any constraint network where the constraints have arity r
or less and tightness of m or less, if the network is strongly ((m+ 1)(r
consistent, then it is globally consistent. Informally, a constraint network is
strongly k-consistent if any instantiation of any k \Gamma 1 or fewer variables that
satisfies the constraints can be extended consistently to any additional variable.
Also informally, given an r-ary constraint and an instantiation of r \Gamma 1 of the
variables that participate in the constraint, the parameter m is an upper bound
AAAI-94 [27].
on the number of instantiations of the rth variable that satisfy the constraint.
In general, such sufficient conditions, bounding the level of local consistency
that guarantees global consistency, are important in applications where constraint
networks are used for knowledge base maintenance and there will be
many queries against the knowledge base. Here, the cost of preprocessing will
be amortized over the many queries. They are also of interest for their explanatory
power, as they can be used for characterizing the difficulty of problems
formulated as constraint networks.
We also show that, in any constraint network where the domains are of size
d or less, and the constraints have looseness of m or greater, the network is
strongly (dd=(d \Gamma m)e)-consistent 2 . Informally, given an r-ary constraint and
an instantiation of r \Gamma 1 of the variables that participate in the constraint, the
parameter m is a lower bound on the number of instantiations of the rth variable
that satisfy the constraint. The bound is straightforward and inexpensive to
determine. In contrast, all but low-order local consistency is expensive to verify
or enforce as the optimal algorithms to enforce k-consistency are O(n k d k ), for
a network with n variables and domains of size at most d [2, 24].
The condition based on constraint looseness is useful in two ways. First, it
can be used in deciding which low-order local consistency techniques will not
change the network and thus are not useful for processing a given constraint
network. For example, we use our results to show that the n-queens problem, a
widely used test-bed for comparing backtracking algorithms, has a high level of
inherent local consistency. As a consequence, it is generally fruitless to preprocess
such a network. Second, it can be used in deciding which local consistency
conditions, if any, still need to be enforced if we want to ensure that a solution
can be found in a backtrack-free manner.
Two definitions of local consistency are employed in characterizing the condi-
tions: the traditional variable-based notion and a recently introduced definition
of local consistency called relational consistency [9, 29].
Definitions and Preliminaries
A constraint network R is a set of n variables fx a domain D i of
possible values for each variable x and a set of t constraint relations
t. Each constraint relation R S i ,
t, is a subset of a Cartesian product of the form
We say that
constrains the variables fx j g. The arity of a constraint relation
is the number of variables that it constrains. The set fS is called the
scheme of R. We assume that S i Because we
assume that variables have names, the order of the variables constrained by a
relation is not important (see [26, pp. 43-45]). We use subsets of the integers
ng and subsets of the variables fx
2 dxe, the ceiling of x, is the smallest integer greater than or equal to x.
ng be a subset of the variables in a constraint network.
An instantiation of the variables in Y is an element of
. Given an
instantiation -a of the variables in Y , an extension of -a to a variable x
is the tuple (-a, a i ), where a i is in the domain of x i .
We now introduce a needed operation on relations adopted from the relational
calculus (see [26] for details).
S be a relation, let S be the set of variables
constrained by R S , and let S 0 ' S be a subset of the variables. The projection of
RS onto the set of variables S 0 , denoted \Pi S 0 (RS ), is the relation which constrains
the variables in S 0 and contains all tuples u 2
D j such that there exists
an instantiation -
a of the variables in S \Gamma S 0 such that the tuple (u; -a) 2 R S .
ng be a subset of the variables in a constraint network. An
instantiation -a of the variables in Y satisfies or is consistent with a relation R S i ,
the tuple \Pi S i (f-ag) 2 R S i . An instantiation -a of the variables in Y is
consistent with a network R if and only if for all S i in the scheme of R such that
a satisfies R S i . A solution to a constraint network is an instantiation
of all n of the variables that is consistent with the network.
constraint relation R of arity k is called m-tight if,
for any variable x i constrained by R and any instantiation -a of the remaining
constrained by R, either there are at most m extensions of -a to
x i that satisfy R, or there are exactly jD i j such extensions.
Definition 3 (m-loose) A constraint relation R of arity k is called m-loose if,
for any variable x i constrained by R and any instantiation -a of the remaining
constrained by R, there are at least m extensions of - a to x i that
satisfy R.
The tightness and looseness properties are complementary properties on the
constraints in a network. Tightness is an upper bound on the number of extensions
and looseness is a lower bound. With the exception of the universal
relation, a constraint relation that is m 1 -loose and m 2 -tight has
case where there are exactly jD i j extensions to variable x i is handled specially in
the definition of tightness). Every constraint relation is 0-loose and a constraint
relation is d-loose if and only if it is the universal relation, where the domains of
the variables constrained by the relation are of size at most d. Every constraint
relation is (d \Gamma 1)-tight and a constraint relation is 0-tight if and only if it is
either the null relation or the universal relation.
In what follows, we are interested in the least upper bound and greatest lower
bound on the number of extensions of the relations of a constraint network. It
is easy to check that:
Given a constraint network with t constraint relations each with
arity at most r and each with at most e tuples in the relation, determining the
least m such that all t of the relations are m-tight requires O(tre) time. The
same bound applies to determining the greatest m such that the relations are
m-loose.
Example 1. We illustrate the definitions using the following network R
with variables fx 1 domains
(b,b,b), (b,c,a), (c,a,b), (c,b,a), (c,c,c)g,
g. The projection of
is given by,
(R (c,c)g.
The instantiation -
(a,c,b) of the variables in is consistent
with R since \Pi S2
. The instantiation of the variables in Y is not consistent with
R since \Pi S2
(a,a,a,b) be an instantiation of all of the variables fx 1 g.
The tuple - a is consistent with R and is therefore a solution of the network. The
set of all solutions of the network is given by,
f(a,a,a,b), (a,a,c,b), (a,b,c,a), (b,a,c,b),
(b,c,a,c), (c,a,b,b), (c,b,a,c), (c,c,c,a)g.
It can be verified that all of the constraints are 2-tight and 1-loose. As
a partial verification of the binary constraint R S3 , consider the extensions to
variable x 3 given instantiations of the variable x 4 . For the instantiation - a =
(a) of x 4 there is 1 extension to x 3 ; for - a = (b) there are 3 extensions (but
so the definition of 2-tightness is still satisfied); and for - a = (c) there
is 1 extension.
Local consistency has proven to be an important concept in the theory and
practice of constraint networks. We now review previous definitions of local
consistency, which we characterize as variable-based and relation-based.
2.1 Variable-based local consistency
Mackworth [18] defines three properties of networks that characterize local con-
sistency: node, arc, and path consistency. Freuder [10] generalizes this to k-
consistency, which can be defined as follows:
Definition 4 (k-consistency, global consistency) A constraint network R
is k-consistent if and only if given
1. any k \Gamma 1 distinct variables, and
2. any instantiation - a of the variables that is consistent with R,
there exists an extension of -a to any kth variable such that the k-tuple is consistent
with R. A network 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,
where n is the number of variables in the network.
Node, arc, and path consistency correspond to one-, two-, and three-consis-
tency, respectively. Globally consistent networks have the property that a solution
can be found without backtracking [11].
(a)
(b)

Figure

1: (a) not 3-consistent; (b) not 4-consistent
Example 2. We illustrate the definition of k-consistency using the well-known
n-queens problem. The problem is to find all ways to place n-queens on
an n \Theta n chess board, one queen per column, so that each pair of queens does not
attack each other. One possible constraint network formulation of the problem
is as follows: there is a variable for each column of the chess board, x
the domains of the variables are the possible row positions, D
and the binary constraints are that two queens should not attack
each other. Consider the constraint network for the 4-queens problem. It can
be seen that the network is 2-consistent since, given that we have placed a single
queen on the board, we can always place a second queen such that the queens do
not attack each other. However, the network is not 3-consistent. For example,
given the consistent placement of two queens shown in Figure 1a, there is no
way to place a queen in the third column that is consistent with the previously
placed queens. Similarly the network is not 4-consistent (see Figure 1b).
2.2 Relation-based local consistency
In [29], we extended the notions of arc and path consistency to non-binary re-
lations. The new local consistency conditions were called relational arc- and
path-consistency. In [9], we generalized relational arc- and path-consistency to
relational m-consistency. In the definition of relational m-consistency, the relations
rather than the variables are the primitive entities. As we shall see in
subsequent sections, this allows expressing the relationships between the restrictiveness
of the constraints and local consistency in a way that avoids an explicit
reference to the arity of the constraints. The definition below is slightly weaker
than that given in [9].
Definition 5 (relational m-consistency) A constraint network R is relationally
m-consistent if and only if given
1. any m distinct relations R
2. any x 2
3. any instantiation - a of the variables in (
that is consistent
with R,
there exists an extension of - a to x such that the extension is consistent with the
relations. A network is strongly relationally m-consistent if it is relationally
j-consistent for every j - m.
Example 3. Consider the constraint network with variables fx 1
domains
(b,a,c)g.
g. The constraints are not
relationally 1-consistent. For example, the instantiation (a,b,b) of the variables
in is consistent with the network (trivially so, since S 1 6' Y and
does not have an extension to x 5 that satisfies R S1 . Similarly,
the constraints are not relationally 2-consistent. For example, the instantiation
(c,b,a,a) of the variables in fx 1 is consistent with the network (again,
trivially so), but it does not have an extension to x 5 that satisfies both R S1 and
RS2 . If we add the constraints R fx2g fag and R
fbg, the set of solutions of the network does not change, and it can be
verified that the network is both relationally 1- and 2-consistent.
When the constraints are all binary, relational m-consistency is identical
to variable-based (m the conditions are different.
While enforcing variable-based m-consistency can be done in polynomial time,
it is unlikely that relational m-consistency can be achieved tractably since even
solves the NP-complete problem of propositional satisfiability (see
Example 6). A more direct argument suggesting an increase in time and space
complexity is the fact that an algorithm may need to record relations of arbitrary
arity. As with variable-based local-consistency, we can improve the efficiency of
enforcing relational consistency by enforcing it only along a certain direction or
linear ordering of the variables. Algorithms for enforcing relational consistency
and directional relational consistency are given in [9, 28].
3 Constraint Tightness vs Global Consistency
In this section, we present relationships between the tightness of the constraints
and the level of local consistency sufficient to ensure that a network is globally
consistent.
Much work has been done on identifying relationships between properties of
constraint networks and the level of local consistency sufficient to ensure global
consistency. This work falls into two classes: identifying topological properties
of the underlying graph of the network (e.g., [7, 8, 11, 12]) and identifying
properties of the constraints (e.g., [3, 15, 16, 21, 29]). Dechter [5] identifies
the following relationship between the size of the domains of the variables, the
arity of the constraints, and the level of local consistency sufficient to ensure
the network is globally consistent.
Theorem 1 (Dechter [5]) If a constraint network with domains that are of
size at most d and relations that are of arity at most r is strongly
consistent, then it is globally consistent.
For some networks, Dechter's theorem is tight in that the level of local consistency
specified by the theorem is really required (graph coloring problems formulated
as constraint networks are an example). For other networks, Dechter's
theorem overestimates. Our results should be viewed as an improvement on
Dechter's theorem. By taking into account the tightness of the constraints, our
results always specify a level of strong consistency that is less than or equal to
the level of strong consistency required by Dechter's theorem.
The following lemma is needed in the proof of the main result.
l be l relations that constrain a variable x, let d be
the size of the domain of variable x, and let - a be an instantiation of all of
the variables except for x that are constrained by the l relations (i.e., -
a is an
instantiation of the variables in (S 1 [
1. each relation is m-tight, for some
2. for every subset of fewer relations from fR l g, there
exists at least one extension of -
a to x that satisfies each of the relations
in the subset,
then there exists at least one extension of - a to x that satisfies all l relations.
Proof. Let a 1 ; a a d be the d elements in the domain of x. We say that
a relation allows an element a i if the extension (-a; a i ) of - a to x satisfies the
relation. Assume to the contrary that an extension of - a to x that satisfies all of
the l relations does not exist. Then, for each element a i in the domain of x there
must exist at least one relation that does not allow a i . Let c i denote one of the
relations that does not allow a i . By construction, the set
is a set of relations for which there does not exist an extension of -a to x that
satisfies each of the relations in the set (every candidate a i is ruled out since c i
does not allow a i ). For every possible value of m, this leads to a contradiction.
Case 1 The contradiction is immediate as is
a set of relations of size m+ 1 for which there does not exist an extension to x
that satisfies every relation in the set. This contradicts condition (2).
Case The nominal size of the set 2.
We claim, however, that there is a repetition in c and that the true size of the
set is m+1. Assume to the contrary that c i 6= c j for i 6= j. Recall c i is a relation
that does not allow a i , g. This is a set
of m+ 1 relations so by condition (2) there must exist an a i that every relation
in the set allows. The only possibility is a d . Now consider fc g.
Again, this is a set of m relations so there must exist an a i that every
relation in the set allows. This time the only possibility is a d\Gamma1 . Continuing in
this manner, we can show that relation c 1 must allow a d ; a
must allow exactly m+1 extensions. This contradicts condition (1). Therefore,
it must be the case that c j. Thus, the set c is of size m
and this contradicts condition (2).
Case 3 The remaining cases are similar.
In each case we argue that (i) there are repetitions in the set
(ii) the true size of the set c is a contradiction is derived by
appealing to condition (2).
Thus, there exists at least one extension of - a to x that satisfies all of the relations.We first state the result using variable-based local consistency and then state
the result using relation-based local consistency.
Theorem 2 If a constraint network with relations that are m-tight and of arity
at most r is strongly ((m+1)(r \Gamma 1)+1)-consistent, then it is globally consistent.
Proof. Let 1. We show that any network with relations
that are m-tight and of arity at most r that is strongly k-consistent is
consistent for any i - 1.
Without loss of generality, let be a set of k
variables, let - a be an instantiation of the variables in X that is consistent with
the constraint network, and let x k+i be an additional variable. Using Lemma 1,
we show that there exists an extension of - a to x k+i that is consistent with the
constraint network. Let R l be l relations which are all and only the
relations which constrain only x k+i and a subset of variables from X. To be
consistent with the constraint network, the extension of -
a to x k+i must satisfy
each of the l relations. Now, condition (1) of Lemma 1 is satisfied since each of
the l relations is m-tight. It remains to show that condition (2) is satisfied. By
definition, the requirement of strong ((m 1)-consistency ensures
that any instantiation of any (m+ 1)(r \Gamma 1) or fewer variables that is consistent
with the network, has an extension to x k+i such that the extension is also
consistent with the network. Note, however, that since each of the l relations is
of arity at most r and constrains x k+i , each relation can constrain at most r \Gamma 1
variables that are not constrained by any of the other relations. Therefore, the
requirement of strong ((m 1)-consistency also ensures that for any
subset of m+1 or fewer relations from fR l g, there exists an extension
of - a to x k+i that satisfies each of the relations in the subset. Thus, condition (2)
of Lemma 1 is satisfied. Therefore, from Lemma 1 it follows that there is an
extension of - a to x k+i that is consistent with the constraint network. 2
Theorem 2 always specifies a level of strong consistency that is less than or
equal to the level of strong consistency required by Dechter's theorem (Theo-
rem 1). The level of required consistency is equal only when
As well, the theorem can sometimes be usefully applied if
theorem cannot.
As the following example illustrates, both r, the arity of the constraints, and
can change if the level of consistency required by the theorem is not present
and must be enforced. The parameter r can only increase; m can decrease,
as shown below, but also increase. The parameter m will increase if all of the
following hold: (i) there previously was no constraint between a set of variables,
(ii) enforcing a certain level of consistency results in a new constraint being
recorded between those variables and, (iii) the new constraint has a larger m
value than the previous constraints.
Example 4. Nadel [22] introduces a variant of the n-queens problem called
confused n-queens. The problem is to find all ways to place n-queens on an n \Theta n
chess board, one queen per column, so that each pair of queens does attack each
other. One possible constraint network formulation of the problem is as follows:
there is a variable for each column of the chess board, x the domains
of the variables are the possible row positions, D
and the binary constraints are that two queens should attack each other. The
constraint relation between two variables x i and x
The problem is worth considering, as Nadel [22] uses confused n-queens
in an empirical comparison of backtracking algorithms for solving constraint
networks. Thus it is important to analyze the difficulty of the problems to set
the empirical results in context. As well, the problem is interesting in that it
provides an example where Theorem 2 can be applied but Dechter's theorem
can not (since d - 1). Independently of n, the constraint relations are all
3-tight. Hence, the theorem guarantees that if the network for the confused
n-queens problem is strongly 5-consistent, the network is globally consistent.
First, suppose that n is even and we attempt to either verify or achieve this
level of strong consistency by applying successively stronger local consistency
algorithms. Kondrak [17] has shown that the following analysis holds for all n,
even.
1. Applying an arc consistency algorithm results in no changes as the network
is already arc consistent.
2. Applying a path consistency algorithm does tighten the constraints between
the variables. Once the network is made path consistent, the constraint
relations are all 2-tight. Now the theorem guarantees that if the
network is strongly 4-consistent, it is globally consistent.
3. Applying a 4-consistency algorithm results in no changes as the network
is already 4-consistent. Thus, the network is strongly 4-consistent and
therefore also globally consistent.
Second, suppose that n is odd. This time, after applying path consistency,
the networks are still 3-tight and it can be verified that the networks are not
4-consistent. Enforcing 4-consistency requires 3-ary constraints. Adding the
necessary 3-ary constraints does not change the value of m; the networks are
still 3-tight. Hence, by Theorem 2, if the networks are strongly 9-consistent, the
networks are globally consistent. Kondrak [17] has shown that recording 3-ary
constraints is sufficient to guarantee that the networks are strongly 9-consistent
for all n, Hence, independently of n, the networks are globally consistent
once strong 4-consistency is enforced.
Recall that Nadel [22] uses confused n-queens problems to empirically compare
backtracking algorithms for finding all solutions to constraint networks.
Nadel states that these problems provide a "non-trivial test-bed" [22, p.190].
We believe the above analysis indicates that these problems are quite easy and
that any empirical results on these problems should be interpreted in this light.
Easy problems potentially make even naive algorithms for solving constraint
networks look promising. To avoid this potential pitfall, backtracking algorithms
should be tested on problems that range from easy to hard. In general,
hard problems are those that require a high level of local consistency to ensure
global consistency. Note also that these problems are trivially satisfiable.
Example 5. The graph k-colorability problem can be viewed as a problem
on constraint networks: there is a variable for each node in the graph, the
domains of the variables are the k possible colors, and the binary constraints are
that two adjacent nodes must be assigned different colors. Graph k-colorability
provides examples of networks where both Theorems 1 and 2 give the same
bound on the sufficient level of local consistency since the constraints are
tight.
We now show how the concept of relation-based local consistency can be
used to alternatively describe Theorem 2.
Theorem 3 If a constraint network with relations that are m-tight is strongly
relationally (m 1)-consistent, then it is globally consistent.
Proof. We show that any network with relations that are m-tight that is
strongly relationally (m + 1)-consistent is k-consistent for any k - 1 and is
therefore globally consistent.
Without loss of generality, let be a set of
let -a be an instantiation of the variables in X that is consistent with the constraint
network, and let x k be an additional variable. Using Lemma 1, we show
that there exists an extension of -a to x k that is consistent with the constraint
network. Let R l be l relations which are all and only the relations
which constrain only x k and a subset of variables from X. To be consistent with
the constraint network, the extension of -a to x k must satisfy each of the l rela-
tions. Now, condition (1) of Lemma 1 is satisfied since each of the l relations is
m-tight. Further, condition (2) of Lemma 1 is satisfied since, by definition, the
requirement of strong relational (m+ 1)-consistency ensures that for any subset
of fewer relations, there exists an extension of -a to x k that satisfies
each of the relations in the subset. Therefore, from Lemma 1 it follows that
there is an extension of - a to x k that is consistent with the constraint network.As an immediate corollary of Theorem 3, if we know that the result of
applying an algorithm for enforcing strong relational (m 1)-consistency will
be that all of the relations will be m-tight, we can guarantee a priori that the
algorithm will return an equivalent, globally consistent network.
Example 6. Consider networks where the domains of the variables are of
size two. For example, the satisfiability of propositional CNFs provide an example
of networks with domains of size two. Relations which constrain variables
with domains of size two are 1-tight and any additional relations that are added
to the network as a result of enforcing strong relational 2-consistency will also be
1-tight. Thus, the consistency of such networks can be decided by an algorithm
that enforces strong relational 2-consistency. A different derivation of the same
result is already given by [5, 29].
A backtracking algorithm constructs and extends partial solutions by instantiating
the variables in some linear order. Global consistency implies that
for any ordering of the variables the solutions to the constraint network can be
constructed in a backtrack-free manner; that is, a backtracking search will not
encounter any dead-ends in the search. Dechter and Pearl [7] observe that it is
often sufficient to be backtrack-free along a particular ordering of the variables
and that local consistency can be enforced with respect to that ordering only.
Frequently, if the property of interest (in our case tightness and looseness) is
satisfied along that ordering we can conclude global consistency restricted to
that ordering as well. Enforcing relational consistency with respect to an ordering
of the variables can be done by a general elimination algorithm called
Directional-Relational-Consistency, presented in [9]. Such an algorithm
has the potential of being more effective in practice and in the worst-case as it
requires weaker conditions. Directional versions of the tightness and looseness
properties and of the results presented in this paper are easily formulated using
the ideas presented in [7, 9].
The results of this section can be used as follows. Mackworth [19] shows
that constraint networks can be viewed as a restricted knowledge representation
and reasoning framework. In this context, solutions of the constraint network
correspond to models of the knowledge base. Our results which bound the
level of local consistency needed to ensure global consistency, can be useful in
applications where constraint networks are used as a knowledge base and there
will be many queries against the knowledge base. Preprocessing the constraint
network so that it is globally consistent means that queries can be answered in
a backtrack-free manner.
An equivalent globally consistent representation of a constraint network is
highly desirable since it compiles the answers to many queries and it can be
shown that there do exist constraint networks and queries against the network
for which there will be an exponential speed-up in the worst case. As an exam-
ple, consider a constraint network with no solutions. The equivalent globally
consistent network would contain only null relations and an algorithm answering
a query against this constraint network would quickly return "yes." Of
course, of more interest are examples where the knowledge base is consistent.
Queries which involve determining if a value for a variable is feasible-can occur
in a model of the network-can be answered from the globally consistent
representation by looking only at the domain of the variable. Queries which
involve determining if the values for a pair of variables is feasible-can both
occur in a single model of the network-can be answered by looking only at
the binary relations which constrain the two variables. It is clear that a general
algorithm to answer a query against the original network, such as backtracking
search, can take an exponential amount of time to answer the above queries. In
general, a globally consistent representation of a network will be useful whenever
it is more compact than the set of all solutions to the network. With the
globally consistent representation we can answer any query on a subset of the
variables Y ' ng by restricting our attention to the smaller network
which consists of only the variables in Y and only the relations which constrain
the variables in Y . The global consistency property ensures that a solution for
all of the variables can also be created in a backtrack-free manner. However,
how our results will work in practice is an interesting empirical question which
remains open.
The results of this section are also interesting for their explanatory power,
as they can be used for characterizing the difficulty of problems formulated as
constraint networks (see the discussion at the end of the next section).
4 Constraint Looseness vs Local Consistency
In this section, we present a sufficient condition, based on the looseness of the
constraints and on the size of the domains of the variables, that gives a lower
bound on the inherent level of local consistency of a constraint network.
It is known that some classes of constraint networks already possess a certain
level of local consistency and therefore algorithms that enforce this level of local
consistency will have no effect on these networks. For example, Nadel [22]
observes that an arc consistency algorithm never changes a constraint network
formulation of the n-queens problem, for n ? 3. Dechter [5] observes that
constraint networks that arise from the graph k-coloring problem are inherently
strongly k-consistent. Our results characterize what it is about the structure of
the constraints in these networks that makes these statements true.
The following lemma is needed in the proof of the main result.
l be l relations that constrain a variable x, let d be
the size of the domain of variable x, and let - a be an instantiation of all of
the variables except for x that are constrained by the l relations (i.e., -
a is an
instantiation of the variables in (S 1 [
1. each relation is m-loose, for some
2. l -
l
d
d\Gammam
there exists at least one extension of -a to x that satisfies all l relations.
Proof. Let a 1 ; a a d be the d elements in the domain of x. We say that
a relation allows an element a i if the extension (-a; a i ) of - a to x satisfies the
relation. Now, the key to the proof is that, because each of the l relations is
m-loose, at least m elements from the domain of x are allowed by each relation.
Thus, each relation does not allow at most d \Gamma m elements, and together the l
relations do not allow at most l(d \Gamma m) elements from the domain of x. Thus, if
it cannot be the case that every element in the domain of x is not allowed by
some relation. Thus, if
l -
d
there exists at least one extension of -
a to x that satisfies all l relations. 2
We first state the result using variable-based local consistency and then
state the result using relation-based local consistency. Let binomial(k; r) be the
binomial coefficients, the number of possible choices of r different elements from
a collection of k objects. If k ! r, then binomial(k;
Theorem 4 A constraint network with domains that are of size at most d and
relations that are m-loose and of arity at least r, r - 2, is strongly k-consistent,
where k is the minimum value such that the following inequality holds,
Proof. Without loss of generality, let be a set of
variables, let - a be an instantiation of the variables in X that is consistent with
the constraint network, and let x k be an additional variable. To show that the
network is k-consistent, we must show that there exists an extension of -a to x k
that is consistent with the constraint network. Let R l be l relations
which are all and only the relations which constrain only x k and a subset of
variables from X. To be consistent with the constraint network, the extension
of - a to x k must satisfy each of the l relations. From Lemma 2, such an extension
exists if l - dd=(d \Gamma m)e \Gamma 1.
Now, the level of strong k-consistency is the minimum number of distinct
variables that can be constrained by the l relations. In other words, k is the
minimum number of variables that can occur in l . We know that
each of the relations constrains the variable x k . Thus, is the
minimum number of variables in (S fxg). The minimum
value of c occurs when all of the relations have arity r and thus each (S
l, is a set of r \Gamma 1 variables. Further, we know that each of the l
relations constrains a different subset of variables; i.e., if i 6= j, then S i
l. The binomial coefficients binomial(c; r \Gamma 1) tell us the number
of distinct subsets of cardinality r \Gamma 1 which are contained in a set of size c.
Thus, us the minimum number of variables c that are
needed in order to specify the remaining r \Gamma 1 variables in each of the l relations
subject to the condition that each relation must constrain a different subset of
variables. 2
Constraint networks with relations that are all binary are an important
special case of Theorem 4.
Corollary 1 A constraint network with domains that are of size at most d and
relations that are binary and m-loose is strongly
d
d\Gammam
-consistent.
Proof. All constraint relations are of arity
2. Hence, the minimum value of k such the inequality in
Theorem 4 holds is when
Theorem 4 always specifies a level of local consistency that is less than or
equal to the actual level of inherent local consistency of a constraint network.
That is, the theorem provides a lower bound. However, given only the looseness
of the constraints and the size of the domains, Theorem 4 gives as strong an
estimation of the inherent level of local consistency as possible as examples can
be given for all m ! d where the theorem is exact. Graph coloring problems
provide an example where the theorem is exact for n-queens
problems provide an example where the theorem underestimates the true level
of local consistency.
Example 7. Consider again the well-known n-queens problem discussed in
Example 2. The problem is of historical interest but also of theoretical interest
due to its importance as a test problem in empirical evaluations of backtracking
algorithms and heuristic repair schemes for finding solutions to constraint
networks (e.g., [13, 14, 20, 22]). For n-queens networks, each of the domains
is of size n and each of the constraints is binary and (n \Gamma 3)-loose. Hence,
Theorem 4 predicts that n-queens networks are inherently strongly (dn=3e)-
consistent. Thus, an n-queens constraint network is inherently arc-consistent
for inherently path consistent for n - 7, and so on, and we can predict
where it is fruitless to apply a low-order consistency algorithm in an attempt to
simplify the network (see Table 1). The actual level of inherent consistency is
bn=2c for n - 7. Thus, for the n-queens problem, the theorem underestimates
the true level of local consistency.

Table

1: Predicted (dn=3e) and actual (bn=2c, for n - 7) level of strong local
consistency for n-queens networks
pred.
actual
Example 8. Graph k-colorability provides an example where Theorem 4
is exact in its estimation of the inherent level of local consistency (see Example
5 for the constraint network formulation of graph coloring). As Dechter [5]
states, graph coloring networks are inherently strongly k-consistent but are not
guaranteed to be strongly 1)-consistent. Each of the domains is of size
k and each of the constraints is binary and 1)-loose. Hence, Theorem 4
predicts that graph k-colorability networks are inherently strongly k-consistent.
Example 9. Consider a formula in 3-CNF which can be viewed as a constraint
network where each variable has the domain ftrue, falseg and each clause
corresponds to a constraint defined by its models. The domains are of size two
and all constraints are of arity 3 and are 1-loose. The minimum value of k such
that the inequality in Theorem 4 holds is when 3. Hence, the networks are
strongly 3-consistent.
We now show how the concept of relation-based local consistency can be
used to alternatively describe Theorem 4.
Theorem 5 A constraint network with domains that are of size at most d and
relations that are m-loose is strongly relationally
d
d\Gammam
-consistent.
Proof. Follows immediately from Lemma 2. 2
The results of this section can be used in two ways. First, they can be used
to estimate whether it would be useful to preprocess a constraint network using
a local consistency algorithm, before performing a backtracking search (see, for
example, [6] for an empirical study of the effectiveness of such preprocessing).
Second, they can be used in conjunction with previous work which has identified
conditions for when a certain level of local consistency is sufficient to ensure a
solution can be found in a backtrack-free manner (see, for example, the brief
review of previous work at the start of Section 3 together with the new results
presented there). Sometimes the level of inherent strong k-consistency guaranteed
by Theorem 4 is sufficient, in conjunction with these previously derived
conditions, to guarantee that the network is globally consistent and therefore a
solution can be found in a backtrack-free manner without preprocessing. Oth-
erwise, the estimate provided by the theorem gives a starting point for applying
local consistency algorithms.
The results of this section are also interesting for their explanatory power.
We conclude this section with some discussion on what Theorem 2 and Theorem
4 contribute to our intuitions about hard classes of problems (in the spirit
of, for example, [1, 30]). Hard constraint networks are instances which give rise
to search spaces with many dead ends. The hardest networks are those where
many dead ends occur deep in the search tree. Dead ends, of course, correspond
to partial solutions that cannot be extended to full solutions. Networks where
the constraints are
that are close to d, the size of the domains of the variables, are good candidates
to be hard problems. The reasons are two-fold. First, networks that have
high looseness values have a high level of inherent strong consistency and strong
k-consistency means that all partial solutions are of at least size k. Second,
networks that have high tightness values require a high level of preprocessing to
be backtrack-free.
Computational experiments we performed on random problems with binary
constraints provide evidence that networks with constraints with high looseness
values can be hard. Random problems were generated with
and is the probability that there is a binary
constraint between two variables, and q=100 is the probability that a pair in
the Cartesian product of the domains is in the constraint. The time to find
one solution was measured. In the experiments we discovered that, given that
the number of variables and the domain size were fixed, the hardest problems
were found when the constraints were as loose as possible without degenerating
into the trivial constraint where all tuples are allowed. In other words, we
found that the hardest region of loose constraints is harder than the hardest
region of tight constraints. That networks with loose constraints would turn
out to be the hardest of these random problems is somewhat counter-intuitive,
as individually the constraints are easy to satisfy. These experimental results
run counter to Tsang's [25, p.50] intuition that a single solution of a loosely
constrained problem "can easily be found by simple backtracking, hence such
problems are easy," and that tightly constrained problems are "harder compared
with loose problems." As well, these hard loosely-constrained problems are not
amenable to preprocessing by low-order local consistency algorithms, since, as
Theorem 4 states, they possess a high level of inherent local consistency. This
runs counter to Williams and Hogg's [30, p.476] speculation that preprocessing
will have the most dramatic effect in the region where the problems are the
hardest.
Conclusions
We identified two new complementary properties on the restrictiveness of the
constraints in a network: constraint tightness and constraint looseness. Constraint
tightness was used, in conjunction with the level of local consistency, in
a sufficient condition that guarantees that a solution to a network can be found
in a backtrack-free manner. The condition can be useful in applications where
a knowledge base will be queried over and over and the preprocessing costs can
be amortized over many queries. Constraint looseness was used in a sufficient
condition for local consistency. The condition is inexpensive to determine and
can be used to estimate the level of strong local consistency of a network. This
in turn can be used in deciding whether it would be useful to preprocess the
network before a backtracking search, and in deciding which local consistency
conditions, if any, still need to be enforced if we want to ensure that a solution
can be found in a backtrack-free manner.
We also showed how constraint tightness and constraint looseness are of interest
for their explanatory power, as they can be used for characterizing the
difficulty of problems formulated as constraint networks and for explaining why
some problems that are "easy" locally, are difficult globally. We showed that
when the constraints have low tightness values, networks may require less pre-processing
in order to guarantee that a solution can be found in a backtrack-free
manner and that when the constraints have high looseness values, networks may
require much more search effort in order to find a solution. As an example, the
confused n-queens problem, which has constraints with low tightness values, was
shown to be easy to solve as it is backtrack-free after enforcing only low-order
local consistency conditions. As another example, many instances of crossword
puzzles are also relatively easy, as the constraints on the words that fit each slot
in the puzzle have low tightness values (since not many words have the same
length and differ only in the last letter of the word). On the other hand, graph
coloring and scheduling problems involving resource constraints can be quite
hard, as the constraints are inequality constraints and thus have high looseness
values.

Acknowledgements

The authors wish to thank Peter Ladkin and an anonymous referee for their
careful reading of a previous version of the paper and their helpful comments.



--R

Where the really hard problems are.
An optimal k-consistency algorithm
Characterising tractable constraints.
Enhancement schemes for constraint processing: Backjump- ing
From local to global consistency.
Experimental evaluation of preprocessing techniques in constraint satisfaction problems.

Tree clustering for constraint networks.
Local and global relational consistency.
Synthesizing constraint expressions.
A sufficient condition for backtrack-free search
A sufficient condition for backtrack-bounded search
Experimental case studies of backtrack vs. waltz-type vs
Increasing tree search efficiency for constraint satisfaction problems.
A test for tractability.
Fast parallel constraint satisfaction.
Personal Communication.
Consistency in networks of relations.
The logic of constraint satisfaction.
Solving large-scale constraint satisfaction and scheduling problems using a heuristic repair method
Networks of constraints: Fundamental properties and applications to picture processing.
Constraint satisfaction algorithms.
Hybrid algorithms for the constraint satisfaction problem.
On the complexity of achieving k-consistency
Foundations of Constraint Satisfaction.
Principles of Database and Knowledge-Base Systems
On the inherent level of local consistency in constraint net- works
Constraint tightness versus global consis- tency
On the minimality and global consistency of row-convex constraint networks
Using deep structure to locate hard problems.
--TR
A sufficient condition for backtrack-bounded search
Principles of database and knowledge-base systems, Vol. I
Network-based heuristics for constraint-satisfaction problems
Tree clustering for constraint networks (research note)
An optimal <italic>k</>-consistency algorithm
Enhancement schemes for constraint processing: backjumping, learning, and cutset decomposition
Constraint satisfaction algorithms
From local to global consistency
The logic of constraint satisfaction
Fast parallel constraint satisfaction
On the inherent level of local consistency in constraint networks
Characterising tractable constraints
Experimental evaluation of preprocessing algorithms for constraint satisfaction problems
On the minimality and global consistency of row-convex constraint networks
Local and global relational consistency
A Sufficient Condition for Backtrack-Free Search
Synthesizing constraint expressions
On the Complexity of Achieving K-Consistency

--CTR
Yuanlin Zhang , Roland H. C. Yap, Erratum: P. van Beek and R. Dechter's theorem on constraint looseness and local consistency, Journal of the ACM (JACM), v.50 n.3, p.277-279, May
Yuanlin Zhang , Roland H. C. Yap, Consistency and set intersection, Eighteenth national conference on Artificial intelligence, p.971-972, July 28-August 01, 2002, Edmonton, Alberta, Canada
Amnon Meisels , Andrea Schaerf, Modelling and Solving Employee Timetabling Problems, Annals of Mathematics and Artificial Intelligence, v.39 n.1-2, p.41-59, September
Paolo Liberatore, Monotonic reductions, representative equivalence, and compilation of intractable problems, Journal of the ACM (JACM), v.48 n.6, p.1091-1125, November 2001
Moshe Y. Vardi, Constraint satisfaction and database theory: a tutorial, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.76-85, May 15-18, 2000, Dallas, Texas, United States
Henry Kautz , Bart Selman, The state of SAT, Discrete Applied Mathematics, v.155 n.12, p.1514-1524, June, 2007
relations;constraint networks;constraint-based reasoning;constraint satisfaction problems;local consistency