On the minimality and global consistency of row-convex constraint networks.
Constraint networks have been shown to be useful in formulating such diverse problems as scene labeling, natural language parsing, and temporal reasoning. Given a constraint network, we often wish to (i) find a solution that satisfies the constraints and (ii) find the corresponding minimal network where the constraints are as explicit as possible. Both tasks are known to be NP-complete in the general case. Task (1) is usually solved using a backtracking algorithm, and task (ii) is often solved only approximately by enforcing various levels of local consistency. In this paper, we identify a property of binary constraint called row convexity and show its usefulness in deciding when a form of local consistency called path consistency is sufficient to guarantee that a network is both minimal and globally consistent. Globally consistent networks have the property that a solution can be found without backtracking. We show that one can test for the row convexity property efficiently and we show, by examining applications of constraint networks discussed in the literature, that our results are useful in practice. Thus, we identify a class of binary constraint networks for which we can solve both tasks (i) and (ii) efficiently. Finally, we generalize the results for binary constraint networks to networks with nonbinary constraints.
Introduction
Constraint networks have been shown to be useful in formulating such diverse
problems as graph coloring [24], scene labeling [16, 28], natural language parsing
[22], and temporal reasoning [1]. A constraint network is defined by a set
of variables, a domain of values for each variable, and a set of constraints between
the variables. Given a constraint network, we often wish to (i) find a
solution-an instantiation of the variables that satisfies the constraints and (ii)
find the corresponding minimal network where the constraints are as explicit as
possible. Finding the minimal network has applications in removing redundant
information from a knowledge base [23] and temporal reasoning [25]. However,
both tasks are known to be NP-complete in the general case. Task (i) is usually
solved using a backtracking algorithm, which is exponential in the worst case
but often useful in practice, and task (ii) is often solved only approximately by
enforcing various levels of local consistency.
In this paper, we begin by examining constraint networks with only binary
constraints. We identify a property of binary constraints called row convexity
and show its usefulness in deciding when a form of local consistency called path
consistency is sufficient to guarantee that a network is both minimaland globally
consistent. Globally consistent networks have the property that a solution can
be found without backtracking. In particular, we show that if a binary constraint
network is path consistent and all of the binary relations are row convex or can
be made row convex, then the network is minimal and globally consistent. We
also show that if there exists an ordering of the variables and of the domains
of the variables such that the binary constraints can be made directionally row
convex, then a solution can be found without backtracking. Testing for the row
convexity property involves determining whether there exists an ordering of the
domains of the variables such that all of the constraints are simultaneously row
convex. We show that one can test for the row convexity property efficiently.
Thus, we identify a class of binary constraint networks for which we can solve
both tasks (i) and (ii) efficiently. We also show, by examining applications of
constraint networks discussed in the literature, that our results are useful in
practice.
Finally, we generalize the results for binary constraint networks to networks
with non-binary constraints. In particular, we generalize the row convexity
property to non-binary constraints and show its usefulness in deciding when a
level of local consistency called strong 2(r r is the
maximum arity of the constraints, is sufficient to ensure that the network is
globally consistent. As well, we generalize the notion of path consistency for
binary constraints to a local consistency condition for non-binary constraints
called relational path-consistency, and use it to identify an interesting class of
non-binary row-convex constraint networks that are globally consistent.
Background
We begin with some needed definitions and describe related work.
(binary constraint networks; Montanari [24])
A network of binary constraints R is a set X of n variables fx 1 ; . ; xng, a
domain D i of possible values for each variable, and a set of binary constraints
between variables. A binary constraint or relation, R ij , between variables x i
and x j , is a subset of the Cartesian product of their domains that specifies the
allowed pairs of values for x i and x j (i.e., R ij ' D i 2D j ). For the networks of
interest here, we require that only if
(solution of a binary constraint network)
An instantiation of the variables in X is an n-tuple representing
an assignment of X i 2 D i to x i . A consistent instantiation of a network is
an instantiation of the variables such that the constraints between variables are
satisfied. A consistent instantiation is also called a solution. A network is
minimal if each pair of values allowed by each of the constraints participates in
at least one consistent instantiation (i.e, if
of some consistent instantiation of the network).
Mackworth [19, 20] defines three properties of networks that characterize
local consistency of networks: node, arc, and path consistency.
Definition 3 (path consistent network; Mackworth [19])
A network is path consistent if and only if, for every triple
ables, we have that, for every instantiation of x i and x j that satisfies the direct
there exists an instantiation of x k such that R ik and R kj are also
Note that the definition of path consistency subsumes arc consistency if in
the above definition we do not assume that variables x i and x j are distinct.
For simplicity, unless otherwise stated, we will assume that path consistency
includes arc consistency. Montanari [24] and Mackworth [19] provide algorithms
for achieving path consistency that also achieve arc consistency. Freuder [12]
generalizes this concept to k-consistency.
Definition 4 (strong k-consistency; Freuder [12, 13])
A network is k-consistent if and only if given any instantiation of any k 0 1
variables satisfying all of the direct relations among those variables, there exists
an instantiation of any kth variable such that the k values taken together satisfy
all of the relations among the k variables. A network is strongly k-consistent if
and only if it is j-consistent for all j - k.
Node, arc, and path consistency correspond to strong one-, two-, and three-
consistency, respectively. A strongly n-consistent network is called globally con-
sistent. Globally consistent networks have the property that any consistent
instantiation of a subset of the variables can be extended to a consistent instantiation
of all of the variables without backtracking [6]. A strongly n-consistent
network is also minimal. However, the converse is not true as it is possible for
a network to be minimal but not strongly n-consistent.
Following Montanari [24], a binary relation R ij between variables x i and x j
is represented as a (0,1)-matrix with jD i j rows and jD j j columns by imposing
an ordering on the domains of the variables. A zero entry at row a column b
means that the pair consisting of the ath element of D i and the bth element
of D j is not permitted; a one entry means that the pair is permitted. Two
distinguished relations are the identity relation, I, which is represented as the
(0,1)-matrix consisting of ones along the diagonal and zeroes everywhere else,
and the universal relation, U , which is represented as a (0,1)-matrix consisting
of all ones.
A concept central to this paper is the row-convexity of constraints.
binary relation R ij represented as a (0,1)-matrix is row convex if and only if
in each row all of the ones are consecutive; that is, no two ones within a single
row are separated by a zero in that same row.
Row convex relations generalize functional and monotone relations. A binary
represented as a (0,1)-matrix is monotone if and only if the following
conditions hold: if R
binary relation R ij represented as a (0,1)-matrix is
functional if and only if there is at most one one in each row and in each column
We use a graphical notation where vertices represent variables and directed
arcs are labeled with the constraints between variables. As a graphical conven-
tion, we never show the edges (i; i), and if we show the edge (i; j), we do not
show the edge (j; i). Any edge for which we have no explicit knowledge of the
constraint is labeled with the universal relation, which is represented as a (0,1)-
matrix consisting of all ones. By convention such edges are also not shown. For
example, consider the simple constraint network with variables x 1 and x 2 and
domains shown below.
'i'j
'i-
The constraint R 12 does not allow, for example, the pair (a; d) but does allow
the pairs (a; e), (a; f). It can be seen that the constraint has the row convexity
property.
2.1 Related work
Much work has been done on identifying restrictions on constraint networks such
that finding a solution and finding the corresponding minimal network can be
done efficiently. These restrictions fall into two classes: restricting the topology
of the underlying graph of the network and restricting the type of the allowed
constraints between variables.
For work that falls into the class of restricting the topology, Montanari [24]
shows that if the constraint graph is a tree, path consistency is sufficient to
ensure that a network is minimal. Freuder [13, 14] identifies a relationship
between a property called the width of a constraint graph and the level of local
consistency needed to ensure that a solution can be found without backtracking.
As a special case, if the constraint graph is a tree, arc consistency is sufficient
to ensure that a solution can be found without backtracking. Dechter and Pearl
[8] provide an adaptive scheme where the level of local consistency is adjusted
on a node-by-node basis. Dechter and Pearl [9] generalize the results on trees to
hyper-trees which are called acyclic databases in the database community [3].
For work that falls into the class of restricting the type of the constraints
(the class into which the present work falls), Dechter [6] identifies a relationship
between the size of the domains of the variables and the level of local consistency
needed to ensure that the network is strongly n-consistent, and thus minimaland
globally consistent. Montanari [24] shows that path consistency is sufficient to
guarantee that a network is both minimal and globally consistent (Montanari
uses the term decomposable) if the relations are monotone. Van Hentenryck,
Deville, and Teng [26] show that arc consistency is sufficient to test whether a
network is satisfiable if the relations are from a restricted class of functional and
monotone constraints. In general, arc consistency is not sufficient to test the
satisfiability of networks with only functional and monotone constraints. To see
this, consider the constraint network that arises from trying to color a complete
graph of three vertices with two colors. The relations are functional and arc
consistent but the network is unsatisfiable. Functional and monotone relations
are row convex; hence, it will be seen that our results generalize Montanari's
and extend Van Hentenryck et al.'s results. Importantly, in the above work, the
problem of deciding whether the constraints have the desired properties is left
to the user. We identify an efficient procedure for deciding whether a constraint
network can be made row convex.
Finally, for work that falls into both classes, Dechter and Pearl [10] present
effective procedures for determining whether a constraint network can be formulated
as a causal theory and thus a solution can be found without backtracking.
Whether a constraint network can be so formulated depends on the topology of
the underlying constraint graph and the type of the constraints.
3 A Sufficient Condition for Minimality and
Global Consistency
In this section we show the usefulness of row convexity in deciding when path
consistency is sufficient to guarantee that a binary network is both minimal
and globally consistent. Informally, we show that if a binary network is path
consistent and the relations are row convex or can be made row convex, then the
network is minimal and globally consistent. We show in Section 4 that a known
procedure from graph theory can be used for deciding whether a constraint
network can be made row convex.
More formally, the following lemma on the intersection of (0,1)-row vectors
that are row convex, is needed in the proof of the result. The lemma is a discrete
version of the well-known result that for a set of mutually intersecting intervals
there is a point common to all.
F be a finite collection of (0,1)-row vectors that are row convex
and of equal length such that every pair of row vectors in F have a non-zero
entry in common; that is, their intersection is not the vector with all zeroes.
Then all of the row vectors in F have a non-zero entry in common.
Proof. Let row vectors of length k. Let first(v i ) and last(v i )
be the position of the first and last one in v i , respectively. For example, if
and last(v i for the zero vector of length k. We want to show that if the
vectors are non-zero and their pairwise intersections are all non-zero, then the
intersection of all of the vectors together is a non-zero vector. The condition
that a vector, v i , is non-zero can be expressed as,
condition that every pair of vectors have a non-zero intersection can be expressed
as, It follows that, max(first(v 1
which is equivalent to saying that the intersection of
all of the vectors together is a non-zero vector. 2
Theorem 1 Let R be a path consistent binary constraint network. If there
exists an ordering of the domains D 1 ; . ; Dn of R such that the relations are
row convex, the network is minimal and globally consistent.
Proof. The theorem is proved by showing that if the network is path consistent
and all of the (0,1)-matrices are row convex, then the network is k-consistent
for all k - n. Hence the network is strongly n-consistent and therefore minimal.
To show that the network is k-consistent for all k - n, we show that it is
true for an arbitrary k. Suppose that variables x 1 ; . ; x k01 can be consistently
instantiated. That is, let be an instantiation such that
is satisfied. To show that the network is k-consistent, we must show that there
exists at least one instantiation, X k , of variable x k such that
is satisfied. We do so as follows. The restrict the allowed instantiations
of x k . For each i in Equation 1, the non-zero entries in row X i of
the (0,1)-matrix R ik are the allowed instantiations of x k . The key is that all
of these row vectors are row convex, i.e., the ones are consecutive. Hence, by
Lemma 1 it is sufficient to show that any two row vectors have a non-zero entry
in common to show that they all have a non-zero entry in common. But arc
consistency guarantees that each row vector contains at least one non-zero entry
and path consistency guarantees that each pair of row vectors has a non-zero
entry in common. Hence, all of the constraints have a non-zero entry in common
and there exists at least one instantiation of x k that satisfies Equation 1 for all
i. Because we require that x j R ji x i , x we have also shown that there
exists at least one instantiation, X k , of variable x k such that
is satisfied. Hence, we have shown that, for any consistent instantiation of k 01
variables, there exists an instantiation of any kth variable such that
is satisfied. Hence, the network is k-consistent. 2
For simplicity, we assumed in the proof of Theorem 1 that all of the domains
of the variables are of equal size. The results are easily generalized to domains
of unequal size. The proof of the theorem is constructive and gives an algorithm
for finding a consistent instantiation. Without loss of generality, we assume the
order of instantiation of the variables is x
Instantiate(R; n)
1. choose an instantiation X 1 of x 1 that satisfies R 11
2. for i / 2 to n
3. do r / [1
4. for
5. do r / r " (row X j of R ji
6. choose an instantiation X i of x i that satisfies r
Intersecting two row vectors in Step 5 takes O(d) time, hence the algorithm is
is the number of variables and d is the size of the domains. The
path consistency procedure is O(d 5 n 3 ) [21] which can be improved to O(d 3
by using a more complicated data structure [15]. So, we can find a solution
and the minimal network for the class of constraint networks characterized by
Theorem 1 in O(d 3
Example 1. Scene labeling in computer vision [5, 16] can be formulated as a
problem on constraint networks. We use an example to illustrate the application
of Theorem 1. Figure 2 shows the variables in the constraint network and
the constraints; Figure 1 shows the domains of the variables and the ordering
imposed. For example, variable x 1 in Figure 2 is a fork and can be instantiated
with any one of the five labelings shown in Figure 1. The constraints between
variables are simply that, if two variables share an edge, then the edge must
be labeled the same at both ends. Not all of the constraints are row convex.
However, once the path consistency algorithm is applied, the relations become
row convex. Therefore, in this example, no reordering of the domains is needed
in order to satisfy the theorem. The Instantiate procedure can be used to
find a solution. The four possible solutions are shown in Figure 3.
Y -Arrow: 000
@ @
@ @
R
Tee:
oe oe
oe oe
oe oeoe oe

Figure

1: Huffman-Clowes junction labelings
The scene-labeling problem has been shown to be NP-complete in the general
case [18]. We are attempting to prove the conjecture that constraint networks
arising from orthohedral scenes are row convex once path consistency is applied.
R 21 =4

Figure

2: Scene labeling constraint network
(a)
-Y

(c)

?(d)

Figure

3: Solutions: (a) stuck on left wall, (b) stuck on right wall, (c) suspended
in mid-air, (d) resting on floor.
As an immediate corollary of Theorem 1, if we know that the result of
applying path consistency will be that all of the relations will be row convex,
we can guarantee a priori that path consistency will find the corresponding
minimal network and that the minimal network will be globally consistent. To
use the path consistency algorithms, three operations on relations are needed:
composition, intersection, and inverse 1 . Thus, if the relations in our constraint
network are row convex and remain row convex under these operations, the
result applies.
Corollary 1 Let L be a set of (0,1)-matrices closed under composition, inter-
section, and transposition such that each element of L is row convex. Let R be a
binary constraint network with all relations taken from L. The path consistency
algorithm will correctly determine the minimal network of R. Furthermore, the
minimal network will be globally consistent.
Proof. This can be proved by a simple rewriting of the proof for Theorem 1.Example 2. Let the domains of the variables be of size two. The set of all
222 (0,1)-matrices is closed under composition, intersection, and transposition
and each 2 2 2 (0,1)-matrix is row convex. Hence, the corollary applies to all
binary constraint networks with domains of size two. As a specific example, the
Graph 2-coloring problem can be formulated using such constraint networks.
Dechter [6, p. 93] also shows, but by a different method, that a strongly 3-
consistent (or path consistent) bi-valued network is minimal.
Example 3. Let the domains of the variables be finite subsets of the integers
and let a binary constraint between two variables be a conjunction of linear
equalities and inequalities of the form
c, where a, b, and c are integer constants. For example, the conjunction
is an allowed constraint between variables x i and x j . A network with constraints
of this form can be formulated as an integer linear program where each constraint
is on two variables and the domains of the variables are restricted to be finite
subsets of the integers. However, it can be shown that each element in the
closure under composition, intersection, and transposition of the resulting set
of (0,1)-matrices is row convex, provided that when an element is removed from
a domain by arc consistency, the associated (0,1)-matrices are "condensed."
This is best illustrated through an example. Let D
ij be the matrix constructed from the constraint
1 When the relations are represented as (0,1)-matrices, these operations correspond to binary
matrix multiplication, binary matrix intersection, and transposition of the matrix, re-
spectively. The reader may consult [19, 24] for details.
jk be constructed from
The matrix R ik , the result of composing R ij and R jk , is not row convex. How-
ever, there is no solution with x k assigned 0, so D k becomes f01; 1g and row
convexity can be restored by removing the middle column from matrices R ik and
R jk . Hence, by Corollary 1 we can guarantee that the result of path consistency
will be the minimal network and the network will be globally consistent. Two
special cases are a restricted and discrete version of Dechter, Meiri, and Pearl's
continuous, bounded difference framework for temporal reasoning and a restricted
and discrete version of Vilain and Kautz's [27] qualitative framework
for temporal reasoning.
Relations
As noted in the scene-labeling example, when constructing a constraint network
and the (0,1)-matrices that represent the constraints, we must impose an ordering
on the domains of the variables. Sometimes a natural ordering exists,
as when the domain is a finite subset of the integers, but often the ordering
imposed is arbitrary and with no inherent meaning. An unlucky ordering may
hide the fact that the constraint network really is row convex or, more properly,
can be made row convex. How can we distinguish this case from the case where
no ordering of the domains will result in row convexity? The following theorem
shows that we can test for this property efficiently.
Theorem 2 (Booth and Lueker [4]) An m2 n (0,1)-matrix specified by its
f nonzero entries can be tested for whether a permutation of the columns exists
such that the matrix is row convex in O(m steps.
Example 4. Maruyama [22] shows that natural language parsing can be
formulated as a problem on constraint networks. In this framework, intermediate
parsing results are represented as a constraint network and every solution
to the network corresponds to an individual parse tree. We use an example
network from [22] to illustrate the application of Theorems 1 and 2. Consider
the following sentence.
Put the block on the floor on the table in the room.
The sentence is structurally ambiguous (there are fourteen different parses) as
there are many ways to attach the prepositional phrases. Figure 4 shows the
original ordering of the domains; Figure 5 shows the variables in the constraint
network and the constraints. For example, the constraint between variable PP3
and variable PP4 is given by the (0,1)-matrix at row PP3 column PP4 of the
table in Figure 5 (the symbol I in the figure denotes the identity matrix-
the (0,1)-matrix consisting of ones along the diagonal and zeroes everywhere
else). Maruyama states that a "simple backtrack search can generate the 14
parse trees of the sentence from the constraint network at any time." While
the network is path consistent, it can be seen that the constraints are not all
row convex given the original domain ordering used in [22]. However, using the
new domain ordering shown in Figure 4, the constraints are now row convex.
Hence, the Instantiate procedure from the previous section can be used to
find a solution in a backtrack-free manner.
Variable Domain
Original ordering New ordering

Figure

4: Variables and domains for parsing example
I
I
I

Figure

5: Left: Parsing constraint network; Right: Table representation of
constraint network
Let R be a path consistent binary constraint network. It remains to show
how Theorem 2 can be used to determine whether an ordering of the domains
of the variables exists such that all of the (0,1)-matrices R ij
row convex. The procedure is simple: for each variable, x j , we take the matrix
defined by stacking up R 1j on top of R 2j on top of 1 1 1 R nj and test whether
the matrix can be made row convex. For example, with reference to Figure 5,
for variable PP4 we would test whether the columns of the matrix consisting of
the 3 columns and 11 rows under the column heading PP4 can be permuted to
satisfy the row convexity property. In this example such a permutation exists
and corresponds to the new ordering of the domain of variable PP4 shown in

Figure

4.
It is, of course, not true that for every path consistent network there exists an
ordering of the domains such that all of the constraints are simultaneously row
convex. However, in those cases where such an ordering does not exist, a weaker
property may hold, where the network is directionally row convex relative to a
particular ordering of the variables.
Definition 6 (directionally row convex)
Given an ordering of the variables x 1 ; . ; xn , a binary constraint network R
is directionally row-convex if each of the (0,1)-matrices R ij , where variable x i
occurs before variable x j in the ordering, is row convex.
Theorem 3 Let R be a path consistent binary constraint network. If there
exists an ordering of the variables x 1 ; . ; xn and of the domains D 1 ; . ; Dn of
R such that R is directionally row convex, then a solution can be found without
backtracking.
Proof. This can be proved by a simple rewriting of the proof for Theorem 1.Example 5. Consider the constraint network with three variables and domains
shown in Figure 6. While this example is
path consistent, no ordering of the domain of x 2 exists that will simultaneously
make the (0,1)-matrices R 12 and R 32 row convex. However, order D
satisfies the condition of Theorem 3 and the variables can be instantiated in the
using the Instantiate procedure, and it can be guaranteed
that no backtracking is necessary 2 .
An algorithm for finding a directionally row convex ordering of the variables
and of their respective domains, if such an ordering exists, is given below.
FindOrder(R;n)
1. L / f1; 2; . ; ng
2. for m / n downto 1
3. do find a j 2 L for which there exists an ordering of
domain D j such that 8i 2 row convex
(if no such j exists, then report failure and halt)
5. put variable x j at position m in the ordering
2 The example was chosen to illustrate the application of the theorem as simply as pos-
sible; in actuality, path consistency is sufficient for guaranteeing the minimality and global
consistency of any three node network.
@
@
@
@ @R
I
I
I

Figure

path consistent network that can be made directionally row
convex; Right: Table representation of constraint network
FindOrder correctly finds a directionally row convex
ordering of the variables and of their respective domains, if such an ordering
exists, in O(d 2 n 3 ) time.
Proof. In the worst-case, Step 3 of the algorithm involves testing, for each of the
n elements of L, whether an nd2d (0,1)-matrix can be made row convex, where
n is the number of variables and d is the size of the domains. By Theorem 2,
each test can be done in O(d 2 n) time, hence the algorithm is O(d 2 n 3 ).
For the proof of correctness, it is sufficient to note that at each stage of the
algorithm, there may be more than one that satisfies the condition (Step
3), but that any j that satisfies the condition for position m in the constructed
ordering will still satisfy the condition for all positions that we
are constructing the ordering in reverse). That is, choosing a j and removing
j from L only makes the problem smaller and simpler, introducing new choices
but never blocking any previously available choices of j. 2
Once (and if) a backtrack-free ordering has been found using the Find-
Order procedure, a solution can be found using the Instantiate procedure.
Recall that a precondition of the algorithms is that the network be path consis-
tent. Ensuring path consistency once again dominates the overall computation
since the complexity of the path consistency procedure is O(d 3 n 3 ) [15]. So, we
can find a solution for the class of constraint networks characterized by Theorem
3 in O(d 3
5 Non-Binary Row-Convex Constraints
In this section we generalize the results for binary row-convex constraint networks
to non-binary row-convex networks. To do this, we generalize row-
convexity from binary relations to r-ary relations, namely relations having r
variables. We first need the following notational conventions and definitions
regarding general networks.
Given a set of variables each associated with a domain of discrete
values respectively, a relation (or, alternatively, a constraint)
R over X is any subset
Given a relation R on a set X of variables and a subset Y ' X, we denote by
y, or by y, an instantiation of the variables in Y , called a subtuple and by
oe Y =y (R) the selection of those tuples in R that agree with y. We denote
by 5Y (R) the projection of the relation R on the subset Y ; that is, a tuple over
Y appears in 5Y (R) if and only if it can be extended to a full tuple in R. The
operator 1 is the join operator of the relational database model.
Definition 8 (constraint networks)
A constraint network R over a set X of variables fx 1 ; . ; xng, is a set of
relations denoted each defined on a subset of variables
respectively. A relation in R specified over Y ' X is also denoted R Y . The
set of subsets on which constraints are specified is called the
scheme of R. The network R represents its set of all consistent solutions over
X, denoted ae(R) or ae(X), namely,
For non-binary networks the notion of consistency of a subtuple can be defined
in several ways. We will use the following definition. A subtuple over Y
is consistent if it satisfies all of the constraints defined over Y or any subsets of
Y .
Definition 9 (consistency of a subtuple)
A subtuple consistent relative to R iff for all S i 2 S, such that S i ' Y ,
where a projection of a tuple y over a set of variables S is the subset of y
restricted to values assigned to S. ae(Y ) is the set of all consistent instantiations
of the variables in Y . One can view ae(Y ) as the set of all solutions of the
subnetwork defined by Y .
Informally, an r-ary relation is row convex if, in the multidimensional matrix
representing the constraint, each vector that is parallel to one of the axes has
the consecutive 1's property.
r-ary relation R on a set X of variables fx 1 ; . ; x r g is row
convex if for any subset of r 0 2 variables Z ' X and for every instantiation,
z, of the variables in Z, the binary relation 5 (X0Z) (oe z (R)) is row convex.
For binary constraint networks, we identified an efficient procedure for determining
whether a domain ordering exists such that the relations are all row
convex (see Section 4). It is an open question whether such an efficient procedure
exists for r-ary constraint networks. However, there are practical examples,
such as bi-valued relations and implicational constraints, where we can assert
that the r-ary relations of a network are all row convex.
Example 6. Any bi-valued relation is row convex since the operations
of selection oe, and projection 5, generate a binary bi-valued relation which is
always row convex. In particular, the set of models of any propositional formula
is row convex. Therefore, formulas given in conjunctive normal form (CNF),
namely as conjunctions of clauses, are row convex constraint networks.
In the following theorem we generalize the results obtained earlier for binary
row-convex constraint networks (Theorem 1) to r-ary row-convex networks.
Theorem 4 Let R be a network of relations whose arity is r or less that is
strongly consistent. If there exists an ordering of the domains
of R such that the relations are row convex, the network is globally
consistent.
Proof. The proof is a simple extension of the ideas in the proof for the binary
case. Assume that the network is strongly 2(r consistent. We show
that for any i - 2(r 2, the network is also i-consistent. Let X
consistent instantiation of i 0 1 variables and let x i be
an arbitrary new variable. We show that there exists a value X i of x i such
that the extended tuple (X consistent. This means that
any relation R t 2 R involving variable x i and a subset of the variables from
of size r01 or less should be satisfied by such an extension. Since
all of the constraints are row convex, all of the values of x i that agree with the
values in X 0 , and that are allowed by R t , can be listed as a row convex vector
relative to the order of x i 's domain.
We claim that any two such constraints have a common consistent value in
Consider two arbitrary constraints, R 1 and R 2 . Let Y
all of the values on which R 1 and R 2 are defined respectively. Since a constraint's
arity is at most r, Y 1 [Y 2 is a consistent subset of values of size at most 2(r 0 1).
Since the problem is strongly 2(r consistent there must exist a value of
x i that satisfies both R 1 and R 2 .
We know, therefore, that any two row vectors corresponding to x i of any
two relevant constraints, intersect. Since they are all row convex they all have a
common value in their intersection. Thus x i can be consistently extended and
the claim is proved. 2
We may be tempted to translate the above condition into a solution procedure
of r-ary row convex network as follows. First enforce strong 2(r
consistency, and then solve the problem in a backtrack-free manner. This, however
will not work in general, since while enforcing 2(r consistency we
may need to record constraints whose arity is greater then r. Consequently, the
resulting network may not be globally consistent.
We now show that the above theorem can be rephrased in terms of a local
consistency condition between constraints that resembles path consistency.
Definition 11 (relational arc and path-consistency)
Let R be a network of relations over a set of variables X, and let RS and RT
be two relations in R, where network is relationally arc-consistent
if for any RS 2 R and for every variable x 2 S,
We say that RS and RT are relationally path-consistent relative to variable x iff
any consistent instantiation of the variables in (S [ has an extension
to x that satisfies RS and RT simultaneously; that is, iff
fxg. (Recall that ae(A) is the set of all consistent instantiations
of the variables in A). A pair of relations R S and R T is relationally
path-consistent iff it is relationally path-consistent relative to each variable in
network of relations is relationally path-consistent iff every pair of
relations is relationally path-consistent.
Note that the definition of relational path-consistency subsumes relational
arc-consistency if in (3) we do not assume distinct pairs of relations. For sim-
plicity, unless otherwise stated, we will assume that relational path-consistency
includes relational arc-consistency.
Example 7. Consider the following CNF formula:
Formula ' can be viewed as a constraint network where each clause corresponds
to a constraint defined by its models. It is easy to see that the clauses are always
relationally arc-consistent since their projection on any subset of propositional
symbols results in the universal relations allowing everything. The first two
clauses are also relationally path-consistent relative to f since any truth assignment
to x; y; z can be extended by assigning "true" to f , thereby satisfying both
clauses. Similarly, the two clauses are relationally path-consistent relative to z
since any consistent assignment to x; y; f has to satisfy the third clause of ' and
therefore by assigning true the first two clauses are satisfied. The reader is
invited to check that the entire set of clauses is relationally path-consistent.
Example 8. Consider the following linear constraints over the non-negative
integers:
The constraints are not relationally arc-consistent. For instance,
satisfies (2), and thus is in ae(f; z), but it cannot be extended to (1). In
order to make constraint (1) relationally arc-consistent we have to add all of
its projections having the form: for any subset T ae ff; x;
1. To make (2) relationally arc-consistent we have to add only z - 1. Once
these sets of linear inequalities are added to (1) and (2) we have relational arc-
consistency. Still we do not have relational path-consistency. For instance, the
instantiation all of the constraints, but it cannot be
consistently extended to a value satisfying (1) and (2). If we add the constraint
constraints (1) and (2) will become relationally path-
consistent relative to z since constraint (3) will disallow the partial assignments
Constraints (1) and (2) are also relationally path-consistent
relative to f since any consistent instantiations of x, y, and z will have to satisfy
the two constraints x that were added to make the
network relationally arc-consistent. Once these constraints are obeyed there is
an extension to that satisfies (1) and (2) simultaneously.
We now show that relational path-consistency is sufficient to ensure global
consistency when the relations are row convex.
Theorem 5 Let R be a network of relations that is relationally path-consistent.
If there exists an ordering of the domains D 1 ; . ; Dn of R such that the relations
are row convex, the network is globally consistent.
Proof. Assume that the network is relationally path-consistent. Let X
consistent instantiation of i 0 1 variables. We show
that for any x i , there exist a value X i of x i such that the extended tuple
consistent. This means that any given applicable relation
that is defined over fx 1 ; . ; x i g should be satisfied. Since all of
the constraints are relationally arc-consistent, they must be consistent with X 0 .
Since they are also row convex, all of the values of x i that are allowed by R Y
and that are restricted to the values in X 0 can be listed as a row convex vector.
Relational path-consistency implies that any two rows corresponding to any
two constraints, must have a common value in their intersection. Since they are
all row convex they all have a common value in their intersection and the claim
is proved. 2
Clearly, when all constraints are binary, relational path-consistency is identical
to path consistency in binary networks. As demonstrated above, relational
path-consistency can be enforced on a network that does not possess this level
of consistency. Below we present algorithm Relational-PC, a brute-force algorithm
for enforcing relational arc- and path-consistency on a network R.
1. repeat
2. Q
3. for every two relations R S , R T 2 Q (not necessarily equal)
and for every x
4. do A / (S
5. RA / RA " 5A (R S 1 R T
The algorithm takes any pair of relations that may or may not be relationally
path-consistent and assures their relational path-consistency by enforcing a relation
(i.e., a constraint) on a subset of their variables. We call the operation
in Step 5 of the algorithm extended composition, since it generalizes the composition
operation defined on binary relations. The Relational-PC algorithm
computes the closure of R with respect to extended composition. If an empty
relation is generated the network is inconsistent. We can conclude that:
Theorem 6 For any network R, whose closure under extended composition is
row convex, Relational-PC will either decide that the network is inconsistent
or else compute an equivalent globally-consistent network of R.
Proof. Follows immediately from Theorem 5 and from the fact that algorithm
Relational-PC generates a relationally path-consistent network. 2.
While enforcing variable-based path-consistency can be done in polynomial
time, it is unlikely that relational path-consistency can be achieved tractably,
since, as we will shortly see, it solves the NP-complete problem of propositional
satisfiability. A more direct argument suggesting an increase in time and
space complexity is the fact that the algorithm may need to record relations
of arbitrary arity. Note that relational arc-consistency can be enforced in time
polynomial in the arity of its constraints.
Example 9. Implicational constraints [17] can be shown to characterize
certain types of scene constraints in vision. These constraints are defined as
follows: A binary constraint R ij , between variables x i and x j , is implicational
if any value of x i either implies the value of x j or it does not constrain it at all,
and vice-versa. A higher order relation is implicational if all of the binary constraints
generated from all projections on all pairs are implicational. It is easy
to see that implicational constraints are necessarily row convex. They generalize
the notions of monotone and functional binary constraints. Consequently,
whenever implicational constraints are closed under extended composition their
consistency can be determined by Relational-PC. Note that the consistency
of implicational constraints can be decided in polynomial time [17].
Example 10. Consider a set of r-ary linear inequalities, where the domains
of the variables are finite subsets of integers and the r-ary constraints over a
subset of variables x 1 are of the form a 1 where the
a i 's are rational constants. This is a general integer linear program. The r-ary
inequalities define corresponding r-ary relations that are row convex. There-
fore, whenever the extended composition of any two of these r-ary relations
can be guaranteed to be row-convex their consistency can be determined by
Relational-PC.
Example 11. Bi-valued relations are row convex and closed under com-
position. Consequently, from Theorem 6, bi-valued networks can be solved by
Relational-PC. In particular, the satisfiability of propositional CNFs can be
decided by Relational-PC. In this case, the composition operation (Step 5
of the Relational-PC algorithm) takes the form of pair-wise resolution. For
more details see [11].
As with variable-based local consistency, we can improve the efficiency of
enforcing relational consistency by enforcing only directional consistency. Below
we present algorithm Directional-Relational-PC, which enforces relational
path-consistency on a network R, relative to a given ordering d of the variables
We will call the network generated by the algorithm the directional
closure of R.
1. for i / n downto 1
2. do for every pair of relations R S and R T (not necessarily distinct)
involving variable x i and any variable x in the ordering d
3. do A / (S
4. RA
5. if RA is the empty relation
6. then exit and return the empty network
While the algorithm is incomplete for deciding consistency in general, it is
complete for row convex relations that are closed under extended composi-
tion. In addition, like similar algorithms for imposing directional consistency,
Directional-Relational-PC's worst-case complexity can be bounded as a
function of the topological structure of the problem via parameters like the
induced width of the graph [8]. We elaborate on these issues below.
Theorem 7 (Completeness) For any network R, whose directional closure
is not empty and row convex, the Directional-Relational-PC algorithm
computes an equivalent network of R that is backtrack-free along the ordering d.
Proof. Clearly the directional closure of R is equivalent to R. What needs
to be shown is that the directional closure relative to d, is backtrack-free along
the ordering d. We will prove this by induction on d. For the first variable x 1
(remember that x 1 is processed last) there must be a value in the domain of x 1
that is allowed since otherwise the domain will be empty and the directional closure
will be empty. Assume now that we have already consistently instantiated
the first i 0 1 variables as X be the next variable.
We claim that (i) every applicable constraint in the directional closure, defined
on x i and a subset of fx 1 ; . ; x i01 g must be consistent with X 0 ; and (ii) any
two such constraints must have a common extension in x i . Otherwise, if (i) is
violated, there is an applicable constraint R , that is not consistent
with X 0 . However, operation (3) of the algorithm in its ith iteration, generates,
R 0 S , a constraint applicable to X 0 that is not satisfied by X 0 , in contradiction
to the assumed consistency of X 0 . If (ii) is violated, then there are two relations
g and R T[fx i
g that are individually consistent with X 0 but have
no common extension in x i . However the extended composition over these two
relation, when x i was processed generated a relation over S [ T that should
have been consulted when testing X 0 's consistency and should have disallowed
yielding a contradiction.
Now that we have established that all pairs of applicable constraints are both
consistent with X 0 and since each pair of applicable relations has a common
extension to x i , the row-convexity property guarantees that they all have a
common extension to x i . 2.
It is important to note that for any ordering d, the complexity of the algorithm
can be bounded as a function of its induced width W3(d). A network
of constraints R can be associated with a constraint graph, where each node
is a variable and two variables that appear in one constraint are connected.
A general graph can be embedded in a clique-tree namely, in a graph whose
cliques form a tree-structure. The induced width, W3, of such an embedding
is its maximal clique size and the induced width W3 of an arbitrary graph is
the minimum induced width over all of its tree-embeddings. It is well known
that finding the minimal width embedding is NP-hard [2], nevertheless every
ordering of the variables d, yields a simple to compute upper bound denoted
[9]). The complexity of Directional-Relational-PC along d
can be bounded as a function of W3(d) of its constraint graph. Specifically,
it was shown that the time complexity and size of the network generated by
Directional-Relational-PC along d is O(exp(W3(d)
It is known that finding the induced width of a graph is NP-complete [2],
nevertheless any arbitrary ordering d is associated with a simple bound w3(d)
that can be computed efficiently.
6 Conclusions
Constraint networks have been shown to have many applications. However, two
common reasoning tasks: (i) find a solution that satisfies the constraints and
(ii) find the corresponding minimal network are known to be NP-complete in
the general case. In this paper, we have identified sufficient conditions based
on the row-convexity of the constraints and the level of local consistency that
guarantee that a solution can be found in a backtrack-free manner. For binary
networks, we showed that we can efficiently test whether a network satisfies the
conditions, and when it does, we gave efficient algorithms for solving both tasks
(i) and (ii). We argued, by examining applications of constraint networks in
the literature, that we have identified an interesting and useful special class of
constraint networks.

Acknowledgements

The authors wish to thank the referees for their careful reading of the paper
and their helpful comments.



--R

Maintaining knowledge about temporal intervals.
Complexity of finding an embedding in k-trees
On the desirability of acyclic database schemes.
Testing for the consecutive ones property
On seeing things.
From local to global consistency.
Temporal constraint networks.

Tree clustering for constraint networks.
Directed constraint networks: A relational frame-work for causal modeling
Directional resolution: The Davis-Putnam proce- dure
Synthesizing constraint expressions.
A sufficient condition for backtrack-free search
A sufficient condition for backtrack-bounded search
Comments on Mohr and Henderson's path consistency algorithm.
Impossible objects as nonsense sentences.
Fast parallel constraint satisfaction.
The complexity of recognizing polyhedral scenes.
Consistency in networks of relations.
Constraint satisfaction.
The complexity of some polynomial network consistency algorithms for constraint satisfaction problems.
Structural disambiguation with constraint propagation.
Tree decomposition with applications to constraint processing.
Networks of constraints: Fundamental properties and applications to picture processing.
Reasoning about qualitative temporal information.
A generic arc consistency algorithm and its specializations.
Constraint propagation algorithms for temporal reasoning.
Understanding line drawings of scenes with shadows.
--TR
The complexity of some polynomial network consistency algorithms for constraint satisfaction problems
A sufficient condition for backtrack-bounded search
Complexity of finding embeddings in a <italic>k</>-tree
Network-based heuristics for constraint-satisfaction problems
Comments on Mohr and Henderson''s path consistency algorithm
Tree clustering for constraint networks (research note)
Temporal constraint networks
From local to global consistency
Reasoning about qualitative temporal information
A generic arc-consistency algorithm and its specializations
Fast parallel constraint satisfaction
A Sufficient Condition for Backtrack-Free Search
On the Desirability of Acyclic Database Schemes
Maintaining knowledge about temporal intervals
Synthesizing constraint expressions

--CTR
Yuanlin Zhang , Roland H. C. Yap, Incrementally solving functional constraints, Eighteenth national conference on Artificial intelligence, p.973-974, July 28-August 01, 2002, Edmonton, Alberta, Canada
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
Mathias Broxvall , Peter Jonsson , Jochen Renz, Disjunctions, independence, refinements, Artificial Intelligence, v.140 n.1-2, p.153-173, September 2002
Hachemi Bennaceur, A Comparison between SAT and CSP Techniques, Constraints, v.9 n.2, p.123-138, April 2004
Peter van Beek , Rina Dechter, Constraint tightness and looseness versus local and global consistency, Journal of the ACM (JACM), v.44 n.4, p.549-566, July 1997
David Cohen , Peter Jeavons , Richard Gault, New Tractable Classes From Old, Constraints, v.8 n.3, p.263-282, July
David Cohen , Peter Jeavons , Richard Gault, New tractable constraint classes from old, Exploring artificial intelligence in the new millennium, Morgan Kaufmann Publishers Inc., San Francisco, CA,
Claudio Bettini , X. Sean Wang , Sushil Jajodia, Solving multi-granularity temporal constraint networks, Artificial Intelligence, v.140 n.1-2, p.107-152, September 2002
Richard Gault , Peter Jeavons, Implementing a Test for Tractability, Constraints, v.9 n.2, p.139-160, April 2004
Christian Bessiere , Emmanuel Hebrard , Brahim Hnich , Toby Walsh, The Complexity of Reasoning with Global Constraints, Constraints, v.12 n.2, p.239-259, June      2007
Vctor Dalmau, A new tractable class of constraint satisfaction problems, Annals of Mathematics and Artificial Intelligence, v.44 n.1-2, p.61-85, May       2005
David Cohen , Peter Jeavons , Peter Jonsson , Manolis Koubarakis, Building tractable disjunctive constraints, Journal of the ACM (JACM), v.47 n.5, p.826-853, Sept. 2000
consecutive ones property;row convexity;relations;constraint networks;constraint-based reasoning;constraint satisfaction problems;path consistency