Building tractable disjunctive constraints.
Many combinatorial search problems can be expressed as 'constraint satisfaction problems'. This class of problems is known to be NP-hard in general, but a number of restricted constraint classes have been identified which ensure tractability. This paper presents the first general results on combining tractable constraint classes to obtain larger, more general, tractable classes. We give examples to show that many known examples of tractable constraint classes, from a wide variety of different contexts, can be constructed from simpler tractable classes using a general method. We also construct several new tractable classes that have not previously been identified.
INTRODUCTION
Many combinatorial search problems can be expressed as 'constraint satisfaction
problems' [Montanari 1974; Mackworth 1977], in which the aim is to nd an assignment
of values to a given set of variables subject to specied constraints. For ex-
ample, the standard propositional satisability problem [Garey and Johnson 1979]
may be viewed as a constraint satisfaction problem where the variables must be
assigned Boolean values, and the constraints are specied by clauses.
The general constraint satisfaction problem is known to be NP-hard [Montanari
1974; Mackworth 1977]. However, by imposing restrictions on the constraint inter-connections
[Dechter and Pearl 1989; Freuder 1985; Gyssens et al. 1994; Montanari
1974], or on the form of the constraints [Cooper et al. 1994; Jeavons et al. 1997;
Jeavons and Cooper 1995; Kirousis 1993; Montanari 1974; van Beek and Dechter
1995; van Hentenryck et al. 1992], it is possible to obtain restricted versions of the
problem that are tractable.
Now that a number of tractable constraint types have been identied, it is of
considerable interest to investigate how these constraint types can be combined,
to yield more general problem classes that are still tractable. This paper presents
the rst general results of this kind: we identify conditions under which dierent
tractable constraint classes can be combined, in order to construct larger, more
general, tractable constraint classes.
We focus specically on 'disjunctive constraints', that is, constraints which have
the form of the disjunction of two constraints of specied types. We show that
whenever we are given tractable constraint types with certain properties, then the
class of problems involving all possible disjunctions of constraints of these types is
also tractable. This allows new tractable constraint classes to be constructed from
simpler tractable classes, and so extends the range of known tractable constraint
classes.
We give examples to show that many known examples of tractable disjunctive
constraints over both nite and innite domains can be constructed from simpler
classes using these results. In particular, we demonstrate that ve out of the six
tractable classes of Boolean constraints identied by Schaefer in [Schaefer 1978] can
be obtained in this way (see Examples 5, 7 and 9). These include the standard Horn
clauses and Krom clauses of propositional logic. Furthermore, we show that similar
results hold for the 'max-closed' constraints rst identied in [Jeavons and Cooper
1995], the 'connected row-convex' constraints rst identied in [Deville et al. 1997]
(see also [Jeavons et al. 1998]), the ORD-Horn constraints over temporal intervals
described in [Nebel and Burckert 1995], the disjunctive linear constraints over the
real numbers described in [Jonsson and Backstrom 1998; Koubarakis 1996], the
'extended Horn clauses' described in [Chandru and Hooker 1991], and the tractable
set constraints described in [Drakengren 1997; Drakengren and Jonsson 1998; Drak-
engren and Jonsson 1997]. In all of these cases our results lead to simplications
of earlier proofs, and in many cases we are able to generalise the earlier results to
Building Tractable Disjunctive Constraints  3
obtain larger families of tractable constraint classes. We also describe some new
tractable classes of constraints that can be derived from the same results.
The paper is organised as follows. In Section 2 we give the basic denitions
for the constraint satisfaction problem, and dene the notion of a tractable set of
constraints. In Section 3 we describe how sets of constraints can be combined to
form disjunctive constraints, and identify a number of dierent conditions that are
sucient to ensure tractability of these disjunctive constraints. In Section 4 we give
examples to illustrate how these results can be used to establish the tractability of
a wide variety of tractable constraint classes.
2. THE CONSTRAINT SATISFACTION PROBLEM
The 'constraint satisfaction problem' was introduced by Montanari in 1974 [Mon-
tanari 1974] and has been widely studied.
Denition 1. An instance of a constraint satisfaction problem consists of:
|A nite set of variables,
|A set of values, D, (which may be nite or innite);
|A nite set of constraints g.
Each constraint c i is a pair (S i is a set of variables, called
the constraint scope, and R i is a set of (total) functions from S i to D, called the
constraint relation.
The elements of a constraint relation indicate the allowed combinations of simultaneous
values for the variables in the constraint scope. The number of variables in
the scope of a constraint will be called the 'arity' of the constraint. In particular,
unary constraints specify the allowed values for a single variable, and binary constraints
specify the allowed combinations of values for a pair of variables. There is
a unique 'empty constraint', (;; ;), for which the scope and the constraint relation
are both empty.
Note that we are representing constraint relations as sets of functions rather than
the usual representation as sets of tuples. These two representations are clearly
equivalent, since by xing an ordering for the variables in the scope of a constraint,
we can associate each function with a corresponding tuple of values. However, the
use of the functional representation simplies some of the denitions below.
Example 1. When the set of values D is the set of real numbers R, then a relation
on some set of variables, say fu; v; wg, is a set of total functions from fu; v; wg to
R. For example, the following is a typical relation
If we x any ordering on the variables, say (w; then the same relation can be
represented as a set of 3-tuples of real numbers:
A solution to a constraint satisfaction problem instance is a function, f , from the
set of variables of that instance to the set of values, such that for each constraint
the restriction of f to S i , denoted f j S i
, is an element of R i .
4  D.Cohen, P.Jeavons, P.Jonsson, and M. Koubarakis
In order to simplify the presentation we shall make a number of simplifying assumptions
throughout the paper about the way in which constraint satisfaction
problem instances are specied. First, we shall assume that we have a xed countable
universe of possible variable names, and that every variable
occurring in a problem instance is a member of this set. Furthermore, we shall
assume that every variable in a problem instance occurs in the scope of some con-
straint. This means that for any problem instance, the set of variables, V , does not
need to be specied explicitly, but is given by the union of the constraint scopes
of that instance. Finally, we shall assume that the set of values, D, for any instance
does not need to be specied explicitly, but will be understood from the
context. With these assumptions, a constraint satisfaction problem instance can be
specied simply by specifying the corresponding set of constraints. Hence, we shall
talk about 'solutions to a set of constraints'. The set of all solutions to the set of
constraints C will be denoted Sol(C).
In order to determine the computational complexity of a constraint satisfaction
problem we need to specify how the constraints are encoded in nite strings of
symbols. We shall assume in all cases that this representation is chosen so that the
complexity of determining whether a constraint allows a given assignment of values
to the variables in its scope is bounded by a polynomial function of the length of
the representation.
Example 2. Constraint relations may be nite or innite. A constraint with a
constraint relation can be represented simply by giving an explicit list of all
the elements in that relation, but constraints with innite relations clearly cannot.
In both cases it is possible to use a suitable specication language, such as logical
formulas, or linear equations. For example, when the set of possible values for the
variables is ftrue; falseg, representing the Boolean values 'true' and `false', then
the logical formula 'x 1 _ x 2 _:x 3 ' can be used to specify the constraint with scope
and relation
Similarly, when the set of possible values is the real numbers, R, then the equation
can be used to specify the constraint with scope fx 1 and relation
Deciding whether or not a given set of constraints has a solution is known to be
NP-hard in general [Montanari 1974; Mackworth 1977]. In this paper we shall consider
how restricting the allowed constraints aects the complexity of this decision
problem. We therefore make the following denition.
Denition 2. For any set of constraints, , CSP() is dened to be the decision
problem with
Instance:. A nite set of constraints C  .
Question:. Does C have a solution?
If there is some algorithm which solves every instance in CSP() in polynomial
time, then we shall say that CSP() is 'tractable', and refer to as a tractable set
of constraints.
Building Tractable Disjunctive Constraints  5
Example 3. For any set of possible values D, and any pair of variables, x and y,
the binary disequality constraint with scope fx; yg and set of values D is dened
as follows:
denotes the constraint (fx;
Since we are assuming that we have a xed universe of possible variable names,
we can consider the set of all possible binary disequality constraints over D, for all
possible choices of a pair of variables. This set will be denoted 6= D
For any nite set D, the decision problem CSP( 6= D
corresponds precisely to
the Graph jDj-Colourability problem [Garey and Johnson 1979]. This problem
is well-known to be tractable when jDj  2 and NP-complete when jDj  3.
3. TRAC


The remainder of the paper focuses on the complexity of constraint satisfaction
problems involving disjunctive constraints.
We rst dene how individual constraints can be combined disjunctively.
Denition 3. Let c be two constraints with a
common set of possible values D.
The disjunction of c 1 and c 2 , denoted c 1 _ c 2 , is dened as follows:
The idea behind this denition is that an assignment satises the disjunction of
two constraints if it satises either one of them. Note that for any constraint c, the
disjunction of c and the empty constraint, (;; ;), gives c.
Now we dene how a set of disjunctive constraints can be obtained from two
arbitrary sets of constraints over the same set of possible values.
Denition 4. For any two sets of constraints and , with a common set of
possible values, dene the set of constraints  _ as follows:
The set of constraints  _ (read as ' or-cross ') contains the disjunction of each
possible pair of constraints from and .
In many cases of interest and  will both contain the empty constraint, (;; ;),
and in these cases  _  [. In most cases of this kind  _ will be much larger
than [ , and will therefore allow a much richer class of constraint satisfaction
problems to be expressed.
The next example shows that when tractable sets of constraints are combined
using the disjunction operation dened in Denition 4 the resulting set of disjunctive
constraints may or may not be tractable.
Example 4. Let  be the set containing all Boolean constraints which can be
specied by a formula of propositional logic consisting of a single literal (where a
literal is either a variable or a negated variable).
The set of constraints  is clearly tractable, as it is straightforward to verify in
linear time whether a collection of simultaneous literals has a solution.
6  D.Cohen, P.Jeavons, P.Jonsson, and M. Koubarakis
Now consider the set of constraints  _. This set contains all Boolean constraints
specied by a disjunction of 2 literals. The problem CSP( _2 ) corresponds
to the 2-Satisfiability problem, which is well-known to be tractable [Garey and
Johnson 1979].
Finally, consider the set of constraints  _. This set contains all
Boolean constraints specied by a disjunction of 3 literals. The problem CSP( _3 )
corresponds to the 3-Satisfiability problem, which is well-known to be NP-complete
[Garey and Johnson 1979].
In many of the examples below we shall be concerned with constraints that are
specied by disjunctions of an arbitrary number of constraints from a given set. To
provide a uniform notation for such constraints we make the following denition.
Denition 5. For any set of constraints, , dene the set   as follows:
=[
_i
where
The nal piece of machinery that we shall need to deal with disjunctive sets of
constraints is a uniform way to recover the separate components in the disjunction.
Denition 6. For any disjunctive set of constraints  _, we dene two operations
such that for any c 2  _,
We shall assume that the constraints in  _ are represented in such a way that  1
and  2 can be computed in linear time.
In the following sections we identify certain conditions on sets of constraints
and  which are sucient to ensure that  _ is tractable.
3.1 The guaranteed satisfaction property
The rst condition we identify is rather trivial, but it is included here for com-
pleteness, and because it is sucient to show how two of the six tractable classes
of Boolean constraints identied by Schaefer in [Schaefer 1978] can be constructed
from simpler classes.
Denition 7. A set of constraints, , has the guaranteed satisfaction property if
every nite C  has a solution.
Theorem 1. For any sets of constraints and , if has the guaranteed satisfaction
property, then CSP(  _) also has the guaranteed satisfaction property, and
is therefore tractable.
Proof. Every constraint in  _ is of the form c_d for some c 2 and some d 2
. Hence if has the guaranteed satisfaction property, then any problem instance
in CSP(  _) has a solution satisfying the rst disjunct of each constraint.
Example 5. Recall the set of unary Boolean constraints, , dened in Example 4,
which contains all constraints specied by a single literal.
Building Tractable Disjunctive Constraints  7
Let be the subset of  containing only the constraints specied by a single
negative literal.
It is clear that has the guaranteed satisfaction property, since any problem
instance in CSP() has the solution which assigns the value false to all variables.
Hence, by Theorem 1,  _  has the guaranteed satisfaction property and CSP(  _  )
is tractable. This tractable set contains all constraints specied by Boolean clauses
containing at least one negative literal. Examples of such clauses include the following

The constraint relations dened by conjunctions of clauses of this form are precisely
the elements of the rst class of tractable Boolean relations identied by Schaefer
in [Schaefer 1978] (which he calls '0-valid' relations).
A symmetric argument shows that if contains only the constraints specied
by a single positive literal, then CSP(  _  ) is again tractable. This tractable set
contains all constraints specied by Boolean clauses containing at least one positive
literal. The constraint relations dened by conjunctions of clauses of this form are
precisely the elements of the second class of tractable Boolean relations identied
by Schaefer in [Schaefer 1978] (which he calls '1-valid' relations).
Example 6. Let be the set of all constraints specied by a linear disequality
over the real numbers, that is, an expression of the form
where the a i
and b are (real-valued) constants.
It is clear that has the guaranteed satisfaction property, since any problem
instance in CSP() only rules out a nite number of hyperplanes from R n .
Hence, by Theorem 1, for any set of constraints, , over the real numbers,  _
has the guaranteed satisfaction property and CSP(  _  ) is tractable.
For example, let  be the set containing all the constraints in together with
all constraints specied by a single (weak) linear inequality, that is, an expression
of the form
where the a i and b are (real-valued) constants. In this case
_  contains constraints such as the following:
This example should be compared with the similar, but much more signicant,
tractable class dened in Example 13 below.
3.2 The independence property
In this section we identify a rather more subtle condition which can be used to
construct tractable disjunctive constraints. We rst need the following denition:
Denition 8. For any sets of constraints and , dene CSPk( [ ) to be
the subproblem of CSP( [ ) consisting of all instances containing at most k
constraints which are members of .
8  D.Cohen, P.Jeavons, P.Jonsson, and M. Koubarakis
Using this denition, we now dene what it means for one set of constraints to be
'k-independent' with respect to another.
Denition 9. For any sets of constraints and , we say that  is k-independent
with respect to if the following condition holds: any set of constraints C in
solution provided every subset of C belonging to CSPk( [
has a solution.
The intuitive meaning of this denition is that the satisability of any set of constraints
chosen from the set  can be determined by considering those constraints
k at a time, even in the presence of arbitrary additional constraints from . In the
examples below we shall demonstrate that several important constraint types have
the 1-independence property.
A more restricted notion of 1-independence has been widely studied in the literature
of constraint programming, where it has been called simply 'independence'
(see [Lassez and McAloon 1989; Lassez and McAloon 1992; Lassez and McAloon
1991], for example). The earlier property applies to an individual constraint class
containing positive constraints and negative constraints, and has been used in the
development of consistency checking algorithms and canonical forms [Lassez and
McAloon 1991; Lassez and McAloon 1992]. However, we will show below that the
more general notion of 1-independence of one class with respect to another, introduced
here, can be used to prove the tractability of a wide variety of disjunctive
constraint classes for which the earlier notion of independence does not hold.
Consider the algorithm shown in Figure 1 for a function Ind-Solvable which
determines whether or not a nite set of constraints C   _ has a solution.
Ind-Solvable(C: finite subset of  _)
repeat
return true
else
S
endif
return false
Fig. 1. An algorithm for the function Ind-Solvable
The next result shows that Ind-Solvable correctly determines whether or not
a nite set of constraints chosen from  _ has a solution in all cases where  is
1-independent with respect to .
Lemma 1. If C is a nite subset of  _, and  is 1-independent with respect to
, then the function Ind-Solvable dened in Figure 1 correctly determines whether
or not C has a solution.
Building Tractable Disjunctive Constraints  9
Proof. The algorithm shown in Figure 1 clearly terminates, because C is nite.
Assume that C is a nite subset of  _ for some and  such that  is
1-independent with respect to . We rst prove by induction that after every
assignment to S, all of the constraints in S must be satised in order to satisfy the
original set of constraints C.
This is vacuously true after the rst assignment to S, because S is then equal to
the empty set.
At each subsequent assignment, S is augmented with the constraints obtained
by applying  1 to the constraints in X . Now, the elements of X are constraints c
of C such that  2 (c) is incompatible with S. Hence the only way such a c can be
satised together with S is to satisfy the other disjunct of c, that is, the constraint
given by  1 (c). Hence, by the inductive hypothesis, each constraint added to S
must be satised in order to satisfy the original set of constraints C, and the result
follows, by induction.
This result establishes that when Ind-Solvable(C) returns false, C has no
solutions.
Conversely, when Ind-Solvable(C) returns true, then we know that X is empty.
This implies that for each constraint c in C either  1 (c) belongs to S, or else  2 (c)
is compatible with the constraints in S. Now, using the fact that  is 1-independent
with respect to , we conclude that S [ f 2 (c) j c 2 C;  1 (c) 62 Sg has a solution,
and hence C has a solution.
By analysing the complexity of the algorithm in Figure 1 we now establish the
following result:
Theorem 2. For any two sets of constraints and , if CSP1( [ ) is
tractable, and  is 1-independent with respect to , then CSP(  _) is tractable.
Proof. By Lemma 1, it is sucient to show that the algorithm in Figure 1 runs
in polynomial time. We can bound the time complexity of this algorithm as follows.
First note that jSj increases on each iteration of the repeat loop, but jSj is
bounded by jCj since each constraint in S arises from an element of C. Hence there
can be at most jCj iterations of this loop.
Now let l(C) be the length of the string specifying C. During each iteration of
the loop the algorithm determines whether or not there is a solution to S[ 2 (c) for
each c remaining in C. Since this set of constraints is a member of CSP1( [
which is assumed to be tractable, these calculations can each be carried out in
polynomial time in the size of their input. Note also that the length of this input is
less than or equal to l(C). Hence, the time complexity of each of these calculations
is bounded by p(l(C)), for some polynomial p.
At the end of each iteration of the loop the algorithm determines whether or not
there is a solution to S. Since S is also an element of CSP1( [ ), and the
length of the specication of S is less than or equal to l(C), this calculation can
also be carried out in at most p(l(C)) time.
Hence, the total time required to complete the algorithm is O(jCj(jCj+1)p(l(C))),
which is polynomial in the size of the input.
Finally, we show that this result can be extended to arbitrary disjunctions of constraints
in .
P.Jonsson, and M. Koubarakis
Lemma 2. For any set of constraints , if  is 1-independent with respect to ,
then   is also 1-independent with respect to .
Proof. Assume that  is 1-independent with respect to and let C be an
arbitrary nite subset of [   . We need to show that if every subset of C which
belongs to CSP  1( [   ) has a solution, then so does C.
Let C 0 be a maximal subset of C belonging to CSP  1( [   ) and let s be a
solution to C 0 . Since C 0 is maximal, it contains the set C , consisting of all the
constraints in C which are elements of n   , so s is a solution to C . If C 0 also
contains a constraint d 2   , then there must be at least one constraint d 0 in
such that s is a solution to d 0 , by the denition of   . Hence, we can replace d
with a (possibly) more restrictive constraint d 0 2 , without losing the solution s.
If we carry out this replacement for each C 0 , then we have a set of constraints
in CSP( [ ) such that each subset belonging to CSP1( [ ) has a solution.
Now, by the fact that  is 1-independent with respect to , it follows that this
modied set of constraints has a solution, and hence the original set of constraints
C has a solution, which gives the result.
Corollary 1. For any two sets of constraints and , if CSP1( [ ) is
tractable, and  is 1-independent with respect to , then CSP(  _  ) is tractable.
Proof. If
each instance of CSP  1( [   ) only contains at most one disjunctive
constraint belonging to   , and each disjunct of this constraint can be considered
separately in polynomial time.
Furthermore, if  is 1-independent with respect to , then by Lemma 2   is
also 1-independent with respect to .
Hence, Theorem 2 can be applied to and   , giving the result.
Example 7. Recall the set of unary Boolean constraints, , dened in Example 4,
which contains all constraints specied by a single literal.
Let be the subset of  containing only the constraints specied by a single
positive literal, and let ;)g. Let  be the subset of  containing only
the constraints specied by a single negative literal. Note that the set of constraints
, constructed according to Denition 5, is equal to the set of constraints specied
by arbitrary nite disjunctions of negative literals (including the empty disjunction).
Now it is easily shown that  is 1-independent with respect to 0 (since any
collection of positive and negative literals has a solution if and only if all subsets
containing at most one negative literal have a solution). Also,
tractable, since each instance is specied by a conjunction of zero or more positive
literals together with at most one negative literal. Hence, by Corollary 1, we
conclude that 0 _  is tractable. But 0 _  is the set of constraints specied by
a disjunction of literals containing at most one positive literal. Examples of such
clauses include the following:
It is easy to see that CSP( 0 _  ) corresponds exactly to the Horn-Clause Satisfiability
problem [Garey and Johnson 1979]. The constraint relations dened
Building Tractable Disjunctive Constraints  11
by conjunctions of clauses of this form are precisely the elements of the third class
of tractable Boolean relations identied by Schaefer in [Schaefer 1978] (which he
calls 'weakly negative' relations).
By a symmetric argument, it follows that the set of constraints specied by a
disjunction of literals containing at most one negative literal is also a tractable set
of constraints. The constraint relations dened by conjunctions of clauses of this
form are precisely the elements of the fourth class of tractable Boolean relations
identied by Schaefer in [Schaefer 1978] (which he calls 'weakly positive' relations).
We have shown that 1-independence can be used to establish tractability, and further
examples are given in Section 4 below. To conclude this section we show that,
if a set of constraints  is k-independent with respect to a set , for some value of
larger than one, then this may not be sucient to ensure tractability of  _.
Example 8. In this example we construct two sets of constraints, and , such
that CSP2( [ ) is tractable, and  is 2-independent with respect to , but
CSP(  _) is NP-complete.
Recall the set of unary Boolean constraints, , dened in Example 4, which
contains all constraints specied by a single literal.
With these denitions, CSP( [ ) is equivalent to the standard 2-Satisfiability
problem, and hence CSP2( [ ) is tractable. Furthermore, the 2-Satisfiability
problem has the property that 'path-consistency' guarantees global consistency [Jeav-
ons et al. 1998], which implies that any minimal insoluble subset of clauses in an
instance of 2-Satisifiability contains at most two single literals, and hence  is
2-independent with respect to ,
However, as discussed in Example 4, CSP(  _) corresponds to the 3-satisfiability
problem, and is therefore NP-complete.
3.3 The Krom property
In this section we identify a nal sucient condition for constructing tractable
disjunctive constraints.
Denition 10. A set of constraints, , has the Krom property if it is 2-independent
with respect to the empty set.
Note that  has the Krom property if and only if for every nite C   having no
solution, there exists a pair of (not necessarily distinct) constraints c
that has no solution.
The name \Krom property" is chosen to emphasise the close connection with
Krom clauses (i.e., Boolean clauses of length  2) [Denenberg and Lewis 1984],
which will be demonstrated later.
Consider the algorithm shown in Figure 2, for a function Krom-Solvable, which
determines whether or not a nite set of constraints C    _ has a solution.
The next result shows that Krom-Solvable correctly determines whether or not
a nite set of constraints chosen from   _ has a solution in all cases when  has
the Krom property.
Lemma 3. If C is a nite subset of   _, and  has the Krom property, then
the function Krom-Solvable dened in Figure 2 correctly determines whether or
not C has a solution.
12  D.Cohen, P.Jeavons, P.Jonsson, and M. Koubarakis
Krom-Solvable(C: finite subset of   _)
Define a set of Boolean variables fqc j c 2 Pg
A := f(:q c 0 _ :q c 00
then return true
else return false
Fig. 2. An algorithm for a function Krom-Solvable
Proof. We show that the function Krom-Solvable dened in Figure 2 returns
true when applied to C if and only if C has a solution.
only-if:. Assume that Krom-Solvable returns true. This implies that there
exists a satisfying truth assignment, , for A [ B. Dene the set of constraints
We rst show that C 0 has a solution. Since  has the Krom property, C 0 has no
solution only if there exist c has no solution. However,
this cannot happen because  satises the formulae in the set A.
Now, let the function f be a solution of C 0 . For each constraint c 2 C we know
that at least one of  1 (c) and  2 (c) is a member of C 0 , because  satises the
formulae in B. Since f is a solution of C 0 , it follows that f can be extended (if
necessary) to a solution of C (by assigning an arbitrary value to any variable not
constrained by C 0 ).
if:. Assume that C has a solution and let f be any such solution. Dene the
truth assignment  : fq c j c 2 Pg ! ftrue; falseg as follows:
We show that  is a satisfying truth assignment of A[B by considering the elements
of A and B in turn.
(1) For each formula (:q c 0 _ :q c 00 ) 2 A, we know that fc 0 ; c 00 g has no solutions.
Hence it cannot be the case that (q c 0 true, which means that
(:q c _ :q c 0 ) is satised by .
(2) For each formula (q c 0 _ q c 00 know that there is a constraint c 2 C such
that  1 is a solution to C, f satises either c,
c 0 , or both. Hence,  assigns true to at least one of q c 0 ; q c 00 , which means that
satised by .
It follows that A [ B is satisable, so Krom-Solvable returns true.
By analysing the complexity of the algorithm in Figure 2 we now establish the
following result:
Theorem 3. For any set of constraints , if CSP() is tractable, and  has
the Krom property, then CSP(  _) is tractable.
Building Tractable Disjunctive Constraints  13
Proof. By Lemma 3, it is sucient to show that the algorithm in Figure 2 runs
in polynomial time. We can bound the time complexity of this algorithm as follows.
Let C be a nite subset of   _ and let l(C) be the length of the string specifying
C.
Since computing  1 and  2 takes linear time, the set P can be computed in
O(l(C)) time. It contains at most 2jCj elements.
To compute the set A, the algorithm must determine whether or not there is
a solution to fc for every pair of constraints c is an
instance of CSP(), which is assumed to be tractable, these calculations can each
be carried out in polynomial time in the size of their input. Hence the time required
to compute the set A is O(jCj 2  p(l(C))), for some polynomial p. The set A contains
at most jCj(2jCj 1) elements.
The set B can clearly be computed in time O(jCjl(C)) and contains jCj elements.
Finally, the algorithm must decide the satisability of a set of Krom clauses
containing at most jCj(2jCj 1)+ jCj elements. By using the linear time algorithm
for this problem given in [Aspvall et al. 1979], this step can be carried out in O(jCj 2 )
time.
Hence, the total time required by the algorithm is O(jCj 2  p(l(C))), which is
polynomial in the size of the input.
The proof of Theorem 3 uses the well-known result about the tractability of solving
Krom clauses. The next example shows that these two results are equivalent.
Example 9. Recall the set of unary Boolean constraints, , dened in Example 4,
which contains all constraints specied by a single literal.
It is easily shown that  has the Krom property (since any collection of positive
and negative literals has a solution unless it contains two dierent literals involving
the same variable). Hence, by Theorem 3,   _ is tractable.
However, the set   _ contains all constraints specied by Boolean clauses containing
at most two literals, that is, all Krom clauses.
The constraint relations dened by conjunctions of clauses of this form are precisely
the elements of the fth class of tractable Boolean relations identied by
Schaefer in [Schaefer 1978] (which he calls 'bijunctive' relations).
To conclude this section we show that if a set of constraints  has a higher level
of k-independence with respect to the empty set, then this may not be sucient to
ensure tractability of   _.
Example 10. In this example we construct a tractable set of relations  such that
is 3-independent with respect to the empty set, but we show that CSP(  _) is
NP-complete.
For all possible variables x and y, we dene the unary constraints zero(x); one(x)
and the binary constraint 6= N (x; y) as follows:
(1) zero(x) denotes the constraint
(2) one(x) denotes the constraint
(3) 6= N (x; y) denotes the constraint (fx;
Dene  to be the set containing all possible constraints of these three types.
(Note that  is well-dened since we are assuming that we have a xed universe of
14  D.Cohen, P.Jeavons, P.Jonsson, and M. Koubarakis
possible variable names.)
Let C be a nite subset of . We will show that if C has no solution, then (at
least) one of the following constraint sets is a subset of C, for some variables x and
y.
To establish this fact, assume that none of the above stated sets of constraints are
subsets of C. We will show that in this case it is always possible to construct a
solution.
Let the set of variables appearing in the constraints of C be g.
Dene the function f
For each constraint c 2 C we can reason as follows:
|Since
|Since c is the constraint 6= N
|Since neither S3 nor S4 is a subset of C, if c is the constraint 6= N
Hence, in all cases c is satised by f , so f is a solution to C.
Since none of the sets S1,S2,S3,S4 contains more than 3 elements, we have
established that  is 3-independent with respect to the empty set, and that  is
tractable.
To establish the NP-completeness of CSP(  _), we construct a polynomial time
reduction from the NP-complete problem 4-Colourability [Garey and Johnson
1979], as follows.
be an arbitrary graph and construct an instance of CSP(  _)
as follows: for each v 2 V , introduce two variables v 0 and v 00 together with the
constraints
For each edge (v; w) 2 E, introduce the constraint
This transformation can obviously be carried out in polynomial time and the resulting
set of constraints is a subset of   _.
To see that the resulting instance has a solution if and only if the graph G is
4-colourable, identify colour 1 with
and so on. For every pair of adjacent nodes v; w in G, the constraint imposed on
the corresponding variables v ensures that v and w must be assigned
dierent colours.
Building Tractable Disjunctive Constraints  15
4. APPLICATIONS
In this section we will use the results established above to demonstrate that many
known tractable sets of constraints can be obtained by combining simpler tractable
sets of constraints using the disjunction operation dened in Denition 4. We will
also describe some new tractable sets of constraints which have not previously been
identied.
Example 11. [Max-closed constraints]
The class of constraints known as 'max-closed' constraints was introduced in [Jeav-
ons and Cooper 1995] and shown to be tractable. This class of constraints has been
used in the analysis and development of a number of industrial scheduling tools [Le-
saint et al. 1998; Purvis and Jeavons 1999].
Max-closed constraints are dened in [Jeavons and Cooper 1995] for arbitrary
nite sets of values which are totally ordered. This class of constraints includes all
of the 'basic constraints' over the natural numbers in the constraint programming
language CHIP [van Hentenryck et al. 1992]. The following are examples of max-
closed constraints when the set of possible values is any nite set of natural numbers:
In this example we will show that the tractability of max-closed constraints is a
simple consequence of Corollary 1. Furthermore, by using Corollary 1 we are able
to generalise this result to obtain tractable constraints over innite sets of values.
Max-closed constraints were originally dened in terms of an algebraic closure
property on the constraint relations [Jeavons and Cooper 1995]. However, it is
shown in [Jeavons and Cooper 1995] that they can also be characterised as those
constraints which can be specied by a conjunction of disjunctions of inequalities
of the following form:
In this expression the x i are variables and the a i are constants.
To apply the results of Section 3.2, let the set of possible values, D, be any totally
ordered set. Dene to be the set of all constraints specied by a single inequality
of the form x i < a i , for some a i 2 D, together with the empty constraint. Dene
to be the set of all constraints specied by a single inequality of the form x i > a i , for
some a i 2 D. Note that the set of constraints   , constructed as in Denition 5, is
equal to the set of constraints specied by arbitrary nite disjunctions of inequalities
of the form x i > a i .
It is easily shown that  is 1-independent with respect to . Also, CSP1( [
is tractable, since each instance consists of a conjunction of upper bounds for individual
variables together with at most one lower bound. Hence, by Corollary 1,
_  is tractable. By the result quoted above, this establishes that max-closed
constraints are tractable.
Unlike the arguments used previously to establish that max-closed constraints
P.Jonsson, and M. Koubarakis
are tractable [Jeavons and Cooper 1995; Jeavons et al. 1995], the argument above
can still be applied when the set of values D is innite.
Example 12. [Connected row-convex constraints]
The class of binary constraints known as 'connected row-convex' constraints was
introduced in [Deville et al. 1997] and shown to be tractable. This class properly
includes the 'monotone' relations, identied and shown to be tractable by Montanari
in [Montanari 1974].
In this example we will show that the tractability of connected row-convex constraints
is a simple consequence of Theorem 3. Furthermore, by using Theorem 3
we are able to generalise this result to obtain tractable constraints over innite sets
of values.
Let the set of possible values D be the ordered set fd 1
. The denition of connected row-convex constraints given in [Deville
et al. 1997] uses a standard matrix representation for binary relations: the binary
relation R over D is represented by the mm 0-1 matrix M , by setting
if the relation contains the pair hd
A relation is said to be connected row-convex if the following property holds:
the pattern of 1's in the matrix representation (after removing rows and columns
containing only 0's) is connected along each row, along each column, and forms a
connected 2-dimensional region (where some of the connections may be diagonal).
Here are some examples of connected row-convex
An alternative characterisation of this class of constraints, in terms of an algebraic
closure property was given in [Jeavons et al. 1998].
Here we obtain another alternative characterisation by noting that the corresponding
matrices have a very restricted structure. If we eliminate all rows and
columns consisting entirely of zeros, and then consider any remaining zero in the
matrix, all of the ones in the same row as the chosen zero must lie one side of it
(because of the connectedness condition on the row). Similarly, all of the ones in
the same column must lie on one side of the chosen zero. Hence there is a complete
path of zeros from the chosen zero to the edge of the matrix along both the row
and column in one direction. But this means there must be a complete rectangular
sub-matrix of zeros extending from the chosen zero to one corner of the matrix
(because of the connectedness condition).
This implies that the whole matrix can be obtained as the intersection (conjunc-
tion) of 0-1 matrices that contain all ones except for a submatrix of zeros in one
corner (simply take one such matrix, obtained as above, for each zero in the matrix
to be constructed).
There are four dierent forms of such matrices, depending on which corner sub-
Building Tractable Disjunctive Constraints  17
matrix is zero, and they correspond to constraints expressed by disjunctive expressions
of the four following forms:
In these expressions x are variables and d i ; d j are constants.
Finally, we note that a row or column consisting entirely of zeros corresponds to
a constraint of the form for an appropriate choice of d 1 and
Hence, any connected row-convex constraint is equivalent to a conjunction of
expressions of these forms.
To apply the results of Section 3.3, dene  to be the set of all unary constraints
specied by a single inequality of the form x i  d i or x i  d i , for some d i 2 D.
It is easily shown that  has the Krom property and CSP() is tractable, since
each instance consists of a conjunction of upper and lower bounds for individual
variables. Hence, by Theorem 3,   _ is tractable. By the alternative characterisation
described above, this establishes that connected row-convex constraints are
tractable.
Unlike the arguments used previously to establish that connected row-convex
constraints are tractable [Deville et al. 1997; Jeavons et al. 1998], the argument
above can still be applied when the set of values D is innite.
Example 13. [Linear Horn constraints]
The class of constraints over the real numbers known as 'linear Horn' constraints
was introduced in [Jonsson and Backstrom 1998; Koubarakis 1996] and shown to
be tractable.
A linear Horn constraint is specied by a disjunction of weak linear inequalities
and linear disequalities where the number of inequalities does not exceed one. The
following are examples of linear Horn constraints:
Linear Horn constraints form an important class of linear constraints with explicit
connections to temporal reasoning [Jonsson and Backstrom 1998]. In particular, the
class of linear Horn constraints properly includes the point algebra of [Vilain et al.
1989], the (quantitative) temporal constraints of [Koubarakis 1992; Koubarakis
1995] and the ORD-Horn constraints of [Nebel and Burckert 1995]. All these
classes of temporal constraints can therefore be shown to be tractable using the
framework developed here.
Let the set of possible values be the real numbers (or the rationals). Dene
to be the set of all constraints specied by a single (weak) linear inequality (e.g.,
together with the empty constraint. Dene  to be the set of
all constraints specied by a single linear disequality (e.g., x 1
P.Jonsson, and M. Koubarakis
Note that   is the set of constraints specied by a disjunction of disequalities,
and the problem CSP( [   ) corresponds to deciding whether a convex polyhe-
dron, possibly minus the union of a nite number of hyperplanes, is the empty set.
It was shown in [Lassez and McAloon 1989] that the set [  is independent (us-
ing their more restrictive notion of independence referred to in Section 3.2, above),
and hence that this problem is tractable.
However, the set of constraints specied by linear Horn constraints corresponds
to the much larger set  _  , and this set is not independent in the sense dened
in [Lassez and McAloon 1989] (see [Koubarakis 1996]). In order to establish that
this larger set of constraints is tractable we shall use the more general notion of
1-independence introduced in this paper.
Consider any set of constraints C in CSP( [ (the subset of
C which is specied by weak linear inequalities), and let C
of C which is specied by linear disequalities). By considering the geometrical
interpretation of the constraints as half spaces and excluded hyperplanes in R n , it
is clear that C is consistent if and only if C 0 is consistent, and, for each c 2 C 00 , the
set consistent (see [Koubarakis 1996]). Hence,  is 1-independent with
respect to .
Now Lemma 2 and Lemma 1 imply that the function Ind-Solvable dened in

Figure

1 can be used to determine whether CSP(  _  ) has a solution. (In fact, the
algorithm in Figure 1 can be seen as a generalisation of the algorithm Consistency
which was developed specically for this problem in [Koubarakis 1996].)
Finally, to establish tractability, we note that whether a set of inequalities, C 0 ,
is consistent or not can be decided in polynomial time, using Khachian's linear
programming algorithm [Khachian 1979]. Furthermore, for any single disequality
constraint, c, we can detect in polynomial time whether C 0 [ fcg is consistent by
simply running Khachian's algorithm to determine whether C 0 implies the negation
of c. Hence, CSP1( [ ) is tractable, so we can apply Corollary 1 and conclude
that CSP(  _  ) is tractable.
Example 14. [Extended Horn clauses]
It was shown by Chandru and Hooker in [Chandru and Hooker 1991] that the
class of Horn clauses may be generalised to a much larger class of tractable sets of
clauses, which they refer to as 'extended Horn clauses'.
To establish that any extended Horn set of clauses can be solved in polynomial
time, Chandru and Hooker give a very indirect argument based on a result from the
theory of linear programming [Chandru and Hooker 1991]. In this example we shall
establish the tractability of a slightly more general class of constraint sets using a
much more direct argument, based on Corollary 1.
In order to dene this new class of tractable constraint sets over Boolean variables,
we rst need to describe how a set of Boolean constraints can be associated with a
tree structure.
Let T be a rooted, undirected, tree in which the edges are labelled with propositional
literals in such a way that each variable name occurs at most once. Note
that T may have an innite number of edges. If we select an edge of T , then it can
be oriented in two dierent ways: either towards the root, or else away from the
root. An edge of T , together with a particular selected orientation, will be called
Building Tractable Disjunctive Constraints  19
an arc of T .
For each possible arc, a, of T we dene an associated literal, in the following
way. If a is oriented away from the root, then we dene the associated literal to be
the label of a in T , otherwise, if a is oriented towards the root, then we dene the
associated literal to be the negation of the label of a in T .
x3
Fig. 3. A labelled tree
For example, let T be the tree shown in Figure 3, with root node n 0 . and consider
the arc from node n 0 to n 1 , denoted [n The literal associated with [n
according to the denition just given, is x 1 . Now consider the arc from node n 5 to
The literal associated with [n 5
Given any set of arcs, we dene an associated clause consisting of the disjunction
of the associated literals. For example, the clause associated with the set of arcs
Some sets of arcs have the special property that they form a path. For example,
in the tree shown in Figure 3, the arcs [n a path of length 2.
The arcs [n 6 a path of length 4.
For any rooted, undirected, tree T , we dene T to be the set of all Boolean
constraints specied by a clause associated with some path in T .
For example, when T is the tree shown in Figure 3, then T includes the clauses
but does not include the clause
or the clause x 1 _ :x 2 .
We rst note that for any tree T , including innite trees, the set of constraints
T is tractable. This is because any instance of CSP( T ) can be solved by the
following polynomial-time algorithm (adapted from [Chandru and Hooker 1991]):
(1) If the instance contains any clauses associated with paths of length one (i.e.,
unit clauses), then assign values to the corresponding variables to satisfy these
20  D.Cohen, P.Jeavons, P.Jonsson, and M. Koubarakis
clauses. If any variable receives contradictory assignments then report that the
instance is insoluble and stop.
(2) If any variables have been assigned values, then remove all clauses which
are satised by these assignments, contract the corresponding edges in T (i.e.,
remove these edges and identify each pair of end points), and return to Step 1.
(3) Report that the problem is soluble. (Since all remaining clauses correspond
to paths of length two or more in T , there is guaranteed to be a solution which
can be obtained by assigning the values true and false alternately along each
branch of T , starting with true.)
However, if we allow disjunctions of constraints in T , then we no longer have
tractability. In fact, we will now show that CSP( T
can be NP-complete.
x3
Fig. 4. A labelled star
This intractability result holds even when the trees are restricted to be stars (that
is, a tree where every edge is incident to the root). Dene Sn to be a star with n
edges labelled x . For example, the star S 5 is shown in Figure 4. Now
consider the innite star, S1 , with edges labelled x :. The set of constraints
consists of all constraints specied by clauses of the form x i , :x i , or x i _:x j ,
for all choices of i and j. Hence the class of constraints S1
_ S1 consists of
all constraints specied by disjunctions of these clauses, or, in other words, by
clauses of the form x
possible choices of i; j; k; l. This set of clauses does not
fall into any of the 6 tractable classes identied by Schaefer in [Schaefer 1978], and
hence the corresponding satisability problem, CSP(S1  _ S1 ), is NP-complete.
Building Tractable Disjunctive Constraints  21
In order to obtain tractable sets of disjunctive constraints, we now identify a
restricted subset of T which is 1-independent with respect to T .
For any rooted, undirected, tree T , we dene  T to be the set of all Boolean
constraints specied by a clause associated with some path in T which ends at the
root node of T .
For example, when T is the tree shown in Figure 3, then  T includes the clauses
but does not include the clause x 4 _ :x 3 , or
the clause :x 5 _ x 1 . As a second example, when T is a star labelled with positive
literals, such as the one shown in Figure 4, then  T consists of all constraints
specied by a single negative literal.
Since  T  T , we can use the same algorithm as before to show that the
problem To show that  T is 1-independent with
respect to T we note that any minimal incompatible subset of clauses can involve
at most one clause from  T . In view of these facts, we can apply Corollary 1 to
conclude that T
_
T is tractable.
Notice that in the special case when T is a star labelled with positive literals the
set of constraints T
_
corresponds precisely to the set of Horn clauses over the
variables labelling T .
In the more general case when T is an arbitrary tree labelled with positive literals,
the set of constraints T
_
T includes the extended Horn set of clauses associated
with T , as dened by Chandru and Hooker [Chandru and Hooker 1991]. Further-
more, in the most general case when T is an arbitrary tree labelled with arbitrary
literals, the set of constraints T
_
T includes the hidden extended Horn clauses
associated with T , as dened by Chandru and Hooker [Chandru and Hooker 1991].
Hence our results are sucient to show that extended Horn clauses and hidden
extended Horn clauses are tractable.
However, we point out that the extended Horn set associated with a tree T , as
dened in [Chandru and Hooker 1991], is a little more restricted than the set of
constraints T
_
T , and hence our result represents a generalisation of the result
in [Chandru and Hooker 1991]. This is because the literals in any clause from
an extended Horn set are required to form an 'extended star-chain' pattern in
the corresponding tree [Chandru and Hooker 1991]. Such a pattern consists of
an arbitrary number of edge disjoint paths terminating at the root node, together
with at most one other path. The literals of the clauses representing constraints in
_
similar patterns, but there is no requirement for the paths into the
root to be disjoint.
For example, when T is the tree shown in Figure 3, then T
_
T includes the
clause :x 1 _:x 2 _:x 3 _x 6 (formed from the disjunction of :x 1 _:x 2 and :x 1 _:x 3
and x 6 ). However, this clause is not in the (hidden) extended Horn set associated
with T .
Example 15. [Extended Krom clauses]
The ideas described in Example 14, together with Theorem 3, can be used to
identify a new class of tractable Boolean constraint sets which we will call 'extended
Krom' sets.
As in Example 14, we associate propositional clauses with sets of arcs in a labelled
tree. Let T be a rooted, undirected tree, whose edges are labelled with propositional
22  D.Cohen, P.Jeavons, P.Jonsson, and M. Koubarakis
literals in such a way that each variable name appears at most once. Note that T
may have an innite number of edges. We dene  T to be the set of all Boolean
constraints specied by a clause associated with some path in T which either starts
or ends at the root node of T .
For example, when T is the tree shown in Figure 3, then  T includes the clauses
but does not include the clause x 4 _:x 3 , or the clause
As a second example, when T is a star labelled with positive literals,
such as the one shown in Figure 4, then  T consists of all constraints specied by
a single positive or negative literal.
The algorithm described in Example 14 can be used to show that CSP( T ) is
tractable. Furthermore, it is easy to show that any set of clauses chosen from  T
is satisable, unless it contains the unit clauses x i and :x i for some i. Hence  T
has the Krom property. In view of these facts, we can apply Theorem 3 to conclude
that  T
_ T is tractable.
Notice that in the special case when T is a star the set of constraints  T
corresponds precisely to the set of Krom clauses over the variables labelling T .
In the more general case when T is an arbitrary tree, the set of constraints
includes a wider variety of clauses. For example, when T is the tree shown
in

Figure

3, then  T includes the following clauses:
Example 16. [Tractable set constraints]
In [Drakengren and Jonsson 1998; Drakengren and Jonsson 1997], Drakengren
and Jonsson identify a number of tractable classes of set constraints that are spec-
ied by expressions involving set-valued variables and the relation symbols , disj
(denoting disjointness) and 6=.
In this example we will show that these tractability results can be obtained as a
simple consequence of Theorem 2. In this way we provide a shorter proof and show
that these results about set constraints conform to one of the general patterns for
tractable disjunctive constraints described in this paper.
We rst give the relevant denitions from [Drakengren and Jonsson 1998; Drak-
engren and Jonsson 1997]. An atomic set constraint or atomic set relation is an
expression of the form x i  x disjunctive set constraint
or disjunctive set relation (DSR) is a disjunction of atomic constraints. A DSR is
called Horn if it consists of zero or more disjuncts of the form x i
and at most one disjunct of the form x i  x j . A DSR is called 2-Horn if it consists
of zero or more disjuncts of the form x i 6= x j and at most one disjunct of the form
. The following are examples of Horn DSRs.
The latter two examples in this list are also 2-Horn.
An -interpretation is a function that maps all set variables in a problem instance
to (possibly empty) sets. An S-interpretation is a function that maps all
Building Tractable Disjunctive Constraints  23
set variables to nonempty sets. An atomic constraint x 1 R x 2 is satised by
an S ; -interpretation (S-interpretation), I , if and only if I(x 1
there exists an S ; -interpretation
which satises some disjunct d i of d. A set C of DSRs is
there exists an S ; -interpretation (S-interpretation)
which satises all members of C. Such a satisfying S ; -interpretation (S-interpretation)
is called an S ; -model (S-model) of C.
The following decision problems are studied in [Drakengren and Jonsson 1998;
Drakengren and Jonsson 1997]:
Instance:. A nite set C of Horn DSRs.
Question:. Does there exist an S ; -model of C?
|HornDSRSat:
Instance:. A nite set C of Horn DSRs.
Question:. Does there exist an S-model of C?
Instance:. A nite set C of 2-Horn DSRs.
Question:. Does there exist an S ; -model of C?
|2HornDSRSat:
Instance:. A nite set C of 2-Horn DSRs.
Question:. Does there exist an S-model of C?
The problem HornDSRSat ; is NP-complete [Drakengren and Jonsson 1998].
To show that the problem HornDSRSat can be solved in polynomial time we
dene to be the set of all constraints specied by expressions of the form x  y
(where x and y are set-valued variables which must be assigned non-empty sets),
together with the empty constraint. We dene  to be the set of all constraints
specied by expressions of the form x 6= y or x disj y (where x and y are set-variables
which must be assigned non-empty sets), together with the empty constraint. Then
is the set of all constraints specied by arbitrary disjunctions of expressions of
the form x 6= y or x disj y.
In [Drakengren and Jonsson 1997] it is shown that the problem of deciding
whether a set of atomic set constraints has an S-model can be solved in polynomial
time. The algorithm presented in [Drakengren and Jonsson 1997] represents set
constraints by a labeled directed graph and essentially consists of two tests. First,
if there is a triple of set variables x; y and z for which the constraints z  x; z  y
and x disj y are implied by the given constraint set, the input set is rejected (because
variable z is forced to be equal to ;). Secondly, if there is a pair of set variables x
and y for which the constraints x  are implied by the given
constraint set, then the input is rejected (because these constraints cannot all be
satised). If a constraint set passes both of these tests then it is accepted.
The existence of this simple algorithm implies that CSP( [ ) and hence also
can be solved in polynomial time. It also implies that  is 1-
independent with respect to . Hence, by Corollary 1 we can immediately conclude
that CSP(  _  ), which corresponds to the decision problem HornDSRSat, can
be solved in polynomial time. In fact the algorithm dened in Figure 1 can be
P.Jonsson, and M. Koubarakis
seen as a generalisation of the iterative version of Algorithm Horn-Sat presented
in [Drakengren and Jonsson 1997].
The problem 2HornDSRSat is a subproblem of HornDSRSat so it can also
be solved in polynomial time.
To show that the decision problem 2HornDSRSat ; can be solved in polynomial
time, dene to be the set of all constraints specied by an expression which is
either of the form x  y or else of the form x disj y (where x and y are set-valued
variables which can be assigned arbitrary sets), together with the empty
constraint. Dene  to be the set of all constraints specied by an expression of
the form x 6= y (where x and y are set-valued variables which can be assigned
arbitrary sets), together with the empty constraint. In this case   is the set of
constraints specied by a disjunction of expressions of the form x 6= y.
In [Drakengren and Jonsson 1998] it is shown that the problem of deciding
whether a set of atomic set constraints has an S ; -model can be solved in polynomial
time. As in the above case, set constraints are represented by a labeled
directed graph. The algorithm proceeds in two steps. First, for any triple of set
variables x; y and z for which the constraints z  x; z  y and x disj y are implied
by the given constraint set, variable z is forced to be equal to ;. Then the
constraints are examined to nd out whether a contradictory triple of constraints
x  implied by the given constraint set. If this is the case,
then the set is rejected. Otherwise, it is accepted.
The existence of this simple algorithm implies that CSP( [ ) and hence also
can be solved in polynomial time. It also implies that  is 1-
independent with respect to . Hence, by Corollary 1 we can immediately conclude
that CSP(  _  ), which now corresponds to the decision problem 2HornDSRSat ; ,
can be solved in polynomial time. As in the above case, the algorithm dened in

Figure

1 can be seen as a generalisation of the iterative version of Algorithm 2-
Horn-Sat presented in [Drakengren and Jonsson 1998].
Having identied the key properties underlying all of these tractable classes, we
are now in a position to identify new tractable classes simply by searching for
appropriate sets of tractable constraints which have these properties.
Example 17. [Disjunctive congruences]
Constraints in the form of congruence relations over the integers are used in a
variety of applications, including the representation of large integers in computer
algebra systems [von zur Gathen and Gerhard 1999], and the representation of
periodic events in temporal databases [Kabanza et al. 1995; Bertino et al. 1998].
One of the fundamental results of elementary number theory is the Chinese Remainder
Theorem [Jackson 1975], which states that a collection of simultaneous
linear congruences
x  a
x  a
x  an (mod mn )
is solvable if and only if the greatest common divisor of m i and m j divides a i a j ,
Building Tractable Disjunctive Constraints  25
for all distinct i and j. When this condition holds between a pair of congruences,
we shall say that they are compatible (Note that compatibility can be decided in
polynomial time.)
Using this result, together with the results established earlier in this paper, we
will construct a number of new tractable classes of constraints.
Let the set of possible values be the set of integers. Dene to be the set of
all unary constraints which are specied by a linear congruence of the form x  a
(mod m), for some natural number a, and some modulus m, together with the
empty constraint. For each natural number b, dene b to be the subset of
containing all unary constraints which are specied by a congruence of the form
x  b (mod m), for some m.
A problem instance in CSP() is specied by a collection of simultaneous congru-
ences. For example, a typical set of constraints in CSP(), involving the variables
x 1 and x 2 , would be:
The Chinese Remainder Theorem implies that any set of constraints in CSP()
has a solution, unless it contains a pair of constraints which are incompatible.
In view of this fact, the results obtained in this paper can be used to construct
tractable disjunctive constraints in the following three ways:
|For any natural number b, it is clear from the denition of compatibility above
that every pair of constraints in b is compatible. Hence, b has the guaranteed
satisfaction property, and by Theorem 1 we conclude that CSP( b
_  ) is
tractable. This means that there is an ecient way to solve any collection of
simultaneous disjunctions of congruences which all have the property that at
least one disjunct comes from b . For example, when have the
following collection:
|For any natural number b, CSP b 1( [ b ) is tractable, because we can determine
whether or not any given instance has a solution in polynomial time by
examining each pair of constraints to see whether they are compatible. Further-
more, no pair of constraints which are both in b can be incompatible, so b
is 1-independent with respect to . Hence, by Corollary 1, we conclude that
b ) is also tractable, for any natural number b. This means that there
is an ecient way to solve any collection of simultaneous disjunctions of congruences
which all have the property that at most one disjunct comes from and
the remainder (if any) from b . For example, when have the
following collection of congruences:
26  D.Cohen, P.Jeavons, P.Jonsson, and M. Koubarakis
|From the observations already made it is clear that the set has the Krom prop-
erty. Hence, by Theorem 3 we conclude that CSP(  _) is tractable. This means
that there is an ecient way to solve any collection of simultaneous disjunctions
of congruences which all contain at most two disjuncts. For example, we might
have the following collection:
Note that the new tractable disjunctive constraints sets constructed in these three
distinct ways are all incomparable with each other.
5. CONCLUSION
In this paper we have established three sucient conditions for tractability of disjunctive
constraints. We have shown that these conditions account for a wide variety
of known tractable constraint classes, over both nite and innite sets of values,
and that they aid the search for new tractable constraint classes. The examples we
have given of new tractable classes obtained in this way are as follows:
|A generalisation of max-closed constraints to innite (ordered) domains (Exam-
ple 11);
|A generalisation of connected row-convex constraints to innite (ordered) domains
(Example 12);
|A (slight) generalisation of extended Horn Clauses (Example 14);
|The new class of extended Krom clauses (Example 15);
|Three new classes of tractable disjunctive congruences (Example 17).
These results provide the rst examples of a constructive approach to obtaining
tractable constraints, based on combining known tractable classes.
This new approach to obtaining tractable classes leads to results of great gener-
ality, as we have shown in this paper. It raises the possibility that on any given
domain there are only a small number of 'basic' tractable constraint types, and all
other tractable constraint classes can be built up from these using a small number
of standard construction techniques.



--R

A linear time algorithm for testing the truth of certain quanti
An access control model supporting periodicity constraints and temporal reasoning.

Tractable disjunctive constraints.

Characterising tractable constraints.

Tree clustering for constraint networks.
The complexity of the satis
Constraint satisfaction over connected row convex constraints.
Algorithms and Complexity for Temporal and Spatial Formalisms.

Qualitative reasoning about sets applied to spatial reasoning.
Reasoning about set constraints applied to tractable inference in intuitionistic logic.

Computers and Intractability: A Guide to the Theory of NP-Completeness
Decomposing constraint satisfaction problems using database techniques.
Number Theory.


A unifying framework for tractable con- straints
Closure properties of constraints.
Tractable constraints on ordered domains.


Journal of Computer and System Sciences
A polynomial time algorithm for linear programming.
Fast parallel constraint satisfaction.
Dense time and temporal constraints with 6
From local to global consistency in temporal constraint networks.


A canonical form for generalized linear constraints.
In TAPSOFT
A constraint sequent calculus.
A canonical form for generalized linear constraints.
Journal of Symbolic Computation
Engineering dynamic scheduler for work manager.
Consistency in networks of relations.
Networks of constraints: Fundamental properties and applications to picture processing.
Reasoning about temporal relations: a maximal tractable subclass of Allen's interval algebra.
Constraint tractability theory and its application to the product development process for a constraint-based scheduler
The complexity of satis
On the minimality and decomposability of row- convex constraint networks
A generic arc-consistency algorithm and its specializations
Constraint propagation algorithms for temporal reasoning: A revised report.
Modern Computer Algebra.
--TR
A sufficient condition for backtrack-bounded search
Tree clustering for constraint networks (research note)
Constraint propagation algorithms for temporal reasoning: a revised report
Extended Horn sets in propositional logic
A canonical form for generalized linear constraints
A generic arc-consistency algorithm and its specializations
A constraint sequent calculus
Fast parallel constraint satisfaction
Decomposing constraint satisfaction problems using database techniques
Characterising tractable constraints
Reasoning about temporal relations
On the minimality and global consistency of row-convex constraint networks
Handling infinite temporal data
Tractable constraints on ordered domains
Closure properties of constraints
Constraints, consistency and closure
A unifying approach to temporal constraint reasoning
An access control model supporting periodicity constraints and temporal reasoning
Modern computer algebra
Computers and Intractability
Engineering Dynamic Scheduler for Work Manager
Independence of Negative Constraints
A Unifying Framework for Tractable Constraints
From Local to Global Consistency in Temporal Constraint Networks
The complexity of satisfiability problems

--CTR
D. A. Cohen, Tractable Decision for a Constraint Language Implies Tractable Search, Constraints, v.9 n.3, p.219-229, July 2004
Mathias Broxvall, A method for metric temporal reasoning, Eighteenth national conference on Artificial intelligence, p.513-518, July 28-August 01, 2002, Edmonton, Alberta, Canada
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,
David Cohen , Peter Jeavons , Richard Gault, New Tractable Classes From Old, Constraints, v.8 n.3, p.263-282, July
Mathias Broxvall , Peter Jonsson , Jochen Renz, Disjunctions, independence, refinements, Artificial Intelligence, v.140 n.1-2, p.153-173, September 2002
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
Andrei Krokhin , Peter Jeavons , Peter Jonsson, Reasoning about temporal relations: The tractable subalgebras of Allen's interval algebra, Journal of the ACM (JACM), v.50 n.5, p.591-640, September
Mathias Broxvall , Peter Jonsson, Point algebras for temporal reasoning: algorithms and complexity, Artificial Intelligence, v.149 n.2, p.179-220, October
constraint satisfaction problem;relations;complexity;NP-completeness;disjunctive constraints;independence