# Building Tractable Disjunctive Constraints.

Abstract. 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.Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems--computations on discrete structures; G.2.1 [Discrete Mathematics]: Combinatorics--combinatorial algorithms; I.2.4 [Artificial Intelligence]: Knowledge Representation Formalisms and Methods--relation systems

General Terms: Algorithms, Theory

Additional Key Words and Phrases: Complexity, constraint satisfaction problem, disjunctive constraints, independence, NP-completeness, relations

1. Introduction

Many combinatorial search problems can be expressed as `constraint satisfaction problems' [Montanari 1974; Mackworth 1977], in which the aim is to find an assignment of values to a given set of variables subject to specified constraints. For example, the standard propositional satisfiability 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 specified by clauses.

The general constraint satisfaction problem is known to be NP-hard [Montanari 1974; Mackworth 1977]. However, by imposing restrictions on the constraint interconnections [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 identified, 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 first general results of this kind: we identify conditions under which different tractable constraint classes can be combined, in order to construct larger, more general, tractable constraint classes.

We focus specifically on `disjunctive constraints', that is, constraints which have the form of the disjunction of two constraints of specified 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 finite and infinite domains can be constructed from simpler classes using these results. In particular, we demonstrate that rive out of the six tractable classes of Boolean constraints identified by 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 first identified in Jeavons and Cooper [1995], the `connected row-convex' constraints first identified 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] and Koubarakis [1996], the `extended Horn clauses' described in Chandru and Hooker [1991], and the tractable set constraints described in Drakengren [1997] and Drakengren and Jonsson [1997; 1998]. In all of these cases our results lead to simplifications of earlier proofs, and in many cases we are able to generalize the earlier results to 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 organized as follows: In Section 2, we give the basic definitions for the constraint satisfaction problem, and define 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 different conditions that are sufficient 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 [1974] and has been widely studied.

Definition 1. An instance of a constraint satisfaction problem consists of:

--A finite set of variables, V;

--A set of values, D, (which may be finite or infinite);

--A finite set of constraints C = {[c.sub.1], [c.sub.2], ..., [c.sub.q]}.

Each constraint [c.sub.i] is a pair ([S.sub.i], [R.sub.i]), where [S.sub.i] [subset or equal to] V is a set of variables, called the constraint scope, and [R.sub.i] is a set of (total) functions from [S.sub.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', (0,0), 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 fixing 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 simplifies some of the definitions 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 {u, v, w}, is a set of total functions from {u, v, w} to R. For example, the following is a typical relation

{f: {u, v, w} [right arrow] R|3u + 2v + w = 0}.

If we fix any ordering on the variables, say (w, u, v), then the same relation can be represented as a set of 3-tuples of real numbers:

{(a, b, c) [element of] [R.sup.3]|a + 3b + 2c = 0}

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 ([S.sub.i], [R.sub.i]) in C, the restriction of f to [S.sub.i], denoted f|[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], is an element of [R.sub.i].

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 specified. First, we shall assume that we have a fixed countable universe of possible variable names, U = {[x.sub.1], [x.sub.2], ...}, 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 constraint. This means that for any problem instance, the set of variables, V, does not need to be specified 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 specified explicitly, but will be understood from the context. With these assumptions, a constraint satisfaction problem instance can be specified 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 finite 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 finite or infinite. A constraint with a finite constraint relation can be represented simply by giving an explicit list of all the elements in that relation, but constraints with infinite relations clearly cannot. In both cases it is possible to use a suitable specification language, such as logical formulas, or linear equations. For example, when the set of possible values for the variables is {TRUE, FALSE}, representing the Boolean values `true' and `false', then the logical formula `[x.sub.1] [disjunction] [x.sub.2] [disjunction] ?? [x.sub.3]' can be used to specify the constraint with scope {[x.sub.1], [x.sub.2], [x.sub.3]} and relation

{f: {[x.sub.1], [x.sub.2], [x.sub.3]} [right arrow] {TRUE, FALSE}|f([x.sub.1]) [disjunction] f([x.sub.2]) [disjunction] ?? f([x.sub.3]) [equivalent] TRUE}.

Similarly, when the set of possible values is the real numbers, R, then the equation `[x.sub.1] + [2x.sub.2] = 7' can be used to specify the constraint with scope {[x.sub.1], [x.sub.2]} and relation

{f: {[x.sub.1], [x.sub.2]} [right arrow] R|f([x.sub.1]) + 2f([x.sub.2])= 7}.

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 affects the complexity of this decision problem. We therefore make the following definition:

Definition 2. For any set of constraints, [Gamma], CSP([Gamma]) is defined to be the decision problem with

Instance: A finite set of constraints C [subset or equal to] [Gamma].

Question: Does C have a solution?

If there is some algorithm that solves every instance in CSP([Gamma]) in polynomial time, then we shall say that CSP([Gamma]) is `tractable', and refer to [Gamma] as a tractable set of constraints.

Example 3. For any set of possible values D, and any pair of variables, x and y, the binary disequality constraint with scope {x, y} and set of values D is defined as follows:

[is not equal to] [sub.D](x, y) denotes the constraint ({x, y}, {f: {x, y} [right arrow] D|f(x) [is not equal to] f(y)}).

Since we are assuming that we have a fixed 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 [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

For any finite set D, the decision problem CSP([MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]) corresponds precisely to the GRAPH |D|-COLORABILITY problem [Garey and Johnson 1979]. This problem is well known to be tractable when |D| [is less than or equal to] 2 and NP-complete when |D| [is greater than or equal to] 3.

3. Tractable Disjunctive Constraints

The remainder of the paper focuses on the complexity of constraint satisfaction problems involving disjunctive constraints.

We first define how individual constraints can be combined disjunctively.

Definition 3. Let [c.sub.1] = ([S.sub.1], [R.sub.1]) and [c.sub.2] = ([S.sub.2], [R.sub.2]) be two constraints with a common set of possible values D.

The disjunction of [c.sub.1] and [c.sub.2], denoted [c.sub.1] [disjunction] [c.sub.2], is defined as follows:

[c.sub.1] [disjunction] [c.sub.2] = ([S.sub.1] [union] [S.sub.2], {f: ([S.sub.1] [union] [S.sub.2]) [right arrow] D|(f| [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] [element of] [R.sub.1]) [disjunction] (f| [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] [element of] [R.sub.2])}).

The idea behind this definition is that an assignment satisfies the disjunction of two constraints if it satisfies either one of them. Note that for any constraint c, the disjunction of c and the empty constraint, (0,0), gives c.

Now we define how a set of disjunctive constraints can be obtained from two arbitrary sets of constraints over the same set of possible values.

Definition 4. For any two sets of constraints [Gamma] and [Delta], with a common set of possible values, define the set of constraints [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] = {[c.sub.1] [disjunction] [c.sub.2]|[c.sub.1] [element of] [Gamma], [c.sub.2] [element of] [Delta]}

The set of constraints [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (read as `[Gamma] or-cross [Delta]') contains the disjunction of each possible pair of constraints from [Gamma] and [Delta].

In many cases of interest, [Gamma] and [Delta] will both contain the empty constraint, (0,0), and in these cases [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] [contains or equal to] [Gamma] [union] [Delta]. In most cases of this kind [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] will be much larger than [Gamma] [union] [Delta], 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 defined in Definition 4 the resulting set of disjunctive constraints may or may not be tractable.

Example 4. Let A be the set containing all Boolean constraints that can be specified 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 A is clearly tractable, as it is straightforward to verify in linear time whether a collection of simultaneous literals has a solution.

Now consider the set of constraints [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. This set contains all Boolean constraints specified by a disjunction of 2 literals. The problem CSP([[Lambda].sup.[disjunction]2]) corresponds to the 2-SATISFIABILITY problem, which is well-known to be tractable [Garey and Johnson 1979].

Finally, consider the set of constraints [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. This set contains all Boolean constraints specified by a disjunction of 3 literals. The problem CSP([[Lambda].sup.[disjunction]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 specified by disjunctions of an arbitrary number of constraints from a given set. To provide a uniform notation for such constraints, we make the following definition.

Definition 5. For any set of constraints, [Delta], define the set [Delta]* as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

where

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for i = 0, 1, 2, ...

The final 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.

Definition 6. For any disjunctive set of constraints [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], we define two operation [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

We shall assume that the constraints in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are represented in such a way that [[Pi].sub.1] and [[Pi].sub.2] can be computed in linear time.

In the following sections, we identify certain conditions on sets of constraints [Gamma] and [Delta] that are sufficient to ensure that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is tractable.

3.1. THE GUARANTEED SATISFACTION PROPERTY. The first condition we identify is rather trivial, but it is included here for completeness, and because it is sufficient to show how two of the six tractable classes of Boolean constraints identified by Schaefer [1978] can be constructed from simpler classes.

Definition 7. A set of constraints, [Gamma], has the guaranteed satisfaction property if every finite C [subset or equal to] [Gamma] has a solution.

THEOREM 1. For any sets of constraints [Gamma] and [Delta], if [Gamma] has the guaranteed satisfaction property, then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] also has the guaranteed satisfaction property, and is therefore tractable.

PROOF. Every constraint in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is of the form c [disjunction] d for some c [element of] [Gamma] and some d [element of] [Delta]. Hence, if [Gamma] has the guaranteed satisfaction property, then any problem instance in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] has a solution satisfying the first disjunct of each constraint. []

Example 5. Recall the set of unary Boolean constraints, [Lambda], defined in Example 4, which contains all constraints specified by a single literal.

Let [Gamma] be the subset of [Lambda] containing only the constraints specified by a single negative literal.

It is clear that [Gamma] has the guaranteed satisfaction property, since any problem instance in CSP([Gamma]) has the solution which assigns the value FALSE to all variables.

Hence, by Theorem 1, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] has the guaranteed satisfaction property and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is tractable. This tractable set contains all constraints specified by Boolean clauses containing at least one negative literal. Examples of such clauses include the following:

[x.sub.1] [disjunction] [x.sub.2] [disjunction] ?? [x.sub.3]

?? [x.sub.2]

?? [x.sub.1] [disjunction] ?? [x.sub.2] [disjunction]?? [x.sub.4] [disjunction] ?? [x.sub.5]

The constraint relations defined by conjunctions of clauses of this form are precisely the elements of the first class of tractable Boolean relations identified by Schaefer [1978] (which he calls `0-valid' relations).

A symmetric argument shows that if [Gamma] contains only the constraints specified by a single positive literal, then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is again tractable. This tractable set contains all constraints specified by Boolean clauses containing at least one positive literal. The constraint relations defined by conjunctions of clauses of this form are precisely the elements of the second class of tractable Boolean relations identified by Schaefer [1978] (which he calls `1-valid' relations).

Example 6. Let [Gamma] be the set of all constraints specified by a linear disequality over the real numbers, that is, an expression of the form [Sigma] [a.sub.i] [x.sub.i] [is not equal to] b, where the [a.sub.i] and b are (real-valued) constants.

It is clear that [Gamma] has the guaranteed satisfaction property, since any problem instance in CSP([Gamma]) only rules out a finite number of hyperplanes from [R.sup.n].

Hence, by Theorem 1, for any set of constraints, [Delta], over the real numbers, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] has the guaranteed satisfaction property and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is tractable.

For example, let [Delta] be the set containing all the constraints in [Gamma] together with all constraints specified by a single (weak) linear inequality, that is, an expression of the form [Sigma] [a.sub.i] [x.sub.i] [is less than or equal to] b, where the [a.sub.i] and b are (real-valued) constants. In this case [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] contains constraints such as the following:

[x.sub.1] + [x.sub.3] + [x.sub.5] [is not equal to] 7,

([3x.sub.1] + [x.sub.5] - [4x.sub.3] [is not equal to] 7) [disjunction] ([2x.sub.1] + [3x.sub.2] - [4x.sub.3] [is not equal to] 4) [disjunction] ([x.sub.2] + [x.sub.3] + [x.sub.5] [is less than or equal to] 7),

([3x.sub.1] + [x.sub.5] - [4x.sub.3] [is not equal to] 7) [disjunction] ([2x.sub.1] + [3x.sub.2] - [4x.sub.3] [is less than or equal to] 4) [disjunction] ([x.sub.2] + [x.sub.3] + [x.sub.5] [is less than or equal to] 7),

([4x.sub.1] + [x.sub.3] [is not equal to] 3) [disjunction] ([5x.sub.2] - [3x.sub.5] + [x.sub.4] [is not equal to] 6).

This example should be compared with the similar, but much more significant, tractable class defined in Example 13 below.

3.2. THE INDEPENDENCE PROPERTY. In this section, we identify a rather more subtle condition that can be used to construct tractable disjunctive constraints. We first need the following definition:

Definition 8. For any sets of constraints [Gamma] and [Delta], define [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] ([Gamma] [union] [Delta]) to be the subproblem of CSP([Gamma] [union] [Delta]) consisting of all instances containing at most k constraints which are members of [Delta].

Using this definition, we now define what it means for one set of constraints to be `k-independent' with respect to another.

Definition 9. For any sets of constraints [Gamma] and [Delta], we say that [Delta] is k-independent with respect to [Gamma] if the following condition holds: Any set of constraints C in CSP([Gamma] [union] [Delta]) bas a solution provided every subset of C belonging to [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] ([Gamma] [union] [Delta]) has a solution.

The intuitive meaning of this definition is that the satisfiability of any set of constraints chosen from the set [Delta] can be determined by considering those constraints k at a rime, even in the presence of arbitrary additional constraints from [Gamma]. 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 bas been called simply `independence' (sec Lassez and McAloon [1989; 1992; 1991], for example). The earlier property applies to an individual constraint class containing positive constraints and negative constraints, and bas been used in the development of consistency checking algorithms and canonical forms [Lassez and McAloon 1991; 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 that determines whether or not a finite set of constraints [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] has a solution.

FIG. 1. An algorithm for the function Ind-Solvable.

Ind-Solvable(C: FINITE SUBSET OF [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]) S := 0 REPEAT X := {c [element of] C | Sol(S [union] [[Pi].sub.2](c)) = 0} IF X = 0 THEN RETURN TRUE ELSE C := C \ X S := S [union] {[[Pi].sub.1] (x) | x [element of] X} ENDIF UNTIL Sol(S) = 0 RETURN FALSE

The next result shows that Ind-Solvable correctly determines whether or not a finite set of constraints chosen from [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] has a solution in all cases where [Delta] is 1-independent with respect to [Gamma].

LEMMA 1. If C is a finite subset of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and [Delta] is 1-independent with respect to [Gamma], then the function Ind-Solvable defined in Figure 1 correctly determines whether or not C has a solution.

PROOF. The algorithm shown in Figure 1 clearly terminates, because C is finite.

Assume that C is a finite subset of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for some [Gamma] and [Delta] such that [Delta] is 1-independent with respect to [Gamma]. We first prove by induction that after every assignment to S, all of the constraints in S must be satisfied in order to satisfy the original set of constraints C.

This is vacuously true after the first 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 [[Pi].sub.1] to the constraints in X. Now, the elements of X are constraints c of C such that [[Pi].sub.2](c) is incompatible with S. Hence the only way such a c can be satisfied together with S is to satisfy the other disjunct of c, that is, the constraint given by [[Pi].sub.1](c). Hence, by the inductive hypothesis, each constraint added to S must be satisfied 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 [[Pi].sub.1](c) belongs to S, or else [[Pi].sub.2](c) is compatible with the constraints in S. Now, using the fact that [Delta] is 1-independent with respect to [Gamma], we conclude that S [union] {[[Pi].sub.2](c)|c [element of] C, [[Pi].sub.1](c) [is not an element of S} has a solution, and hence C has a solution. []

By analyzing the complexity of the algorithm in Figure 1 we now establish the following result:

THEOREM 2. For any two sets of constraints [Gamma] and [Delta], if [CSP.sub.[Delta] [is less than or equal to] 1]([Gamma] [union] [Delta]) is tractable, and [Delta] is 1-independent with respect to [Gamma], then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is tractable.

PROOF. By Lemma 1, it is sufficient 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 |S| increases on each iteration of the repeat loop, but |S| is bounded by |C| since each constraint in S arises from an element of C. Hence, there can be at most |C| 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 [union] [[Pi].sub.1](c) for each c remaining in C. Since this set of constraints is a member of [CSP.sub.[Delta] [is less than or equal to] 1] ([Gamma] [union] [Delta]), 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 [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] ([Gamma] [union] [Delta]), and the length of the specification 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(|C|(|C| + 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 [Delta].

LEMMA 2. For any set of constraints [Delta], if [Delta] is 1-independent with respect to [Gamma], then [Delta]* is also 1-independent with respect to [Gamma].

PROOF. Assume that [Delta] is 1-independent with respect to [Gamma] and let C be an arbitrary finite subset of [Gamma] [union] [Delta]*. We need to show that if every subset of C which belongs to [CSP.sub.[Delta][is less than or equal to] 1] ([Gamma] [union] [Delta]*) has a solution, then so does C.

Let C' be a maximal subset of C belonging to [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] ([Gamma] [union] [Delta]*) and let s be a solution to C'. Since C' is maximal, it contains the set [C.sub.[Gamma]], consisting of all the constraints in C which are elements of [Gamma]\[Delta]*, so s is a solution to [C.sub.[Gamma]]. If C' also contains a constraint d [element of] [Delta]*, then there must be at least one constraint d' in [Delta] such that s is a solution to d', by the definition of [Delta]*. Hence, we can replace d with a (possibly) more restrictive constraint d' [element of] [Delta], without losing the solution s.

If we carry out this replacement for each C', then we have a set of constraints in CSP([Gamma] [union [Delta]) such that each subset belonging to [CSP.sub.[Delta][is less than or equal to] 1] ([Gamma] [union] [Delta]) has a solution. Now, by the fact that [Delta] is 1-independent with respect to [Gamma], it follows that this modified 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 [Gamma] and [Delta], if [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] ([Gamma] [union] [Delta]) is tractable, and [Delta] is 1-independent with respect to [Gamma], then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is tractable.

PROOF. If [CSP.sub.[Delta][is less than or equal to] 1] ([Gamma] [union] [Delta]) is tractable, then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] ([Gamma] [union] [Delta]*) is tractable, because each instance of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] ([Gamma] [union] [Delta]*) only contains at most one disjunctive constraint belonging to [Delta]*, and each disjunct of this constraint can be considered separately in polynomial time.

Furthermore, if [Delta] is 1-independent with respect to [Gamma], then by Lemma 2 [Delta]* is also 1-independent with respect to [Gamma].

Hence, Theorem 2 can be applied to [Gamma] and [Delta]*, giving the result. []

Example 7. Recall the set of unary Boolean constraints, [Lambda], defined in Example 4, which contains all constraints specified by a single literal.

Let [Gamma] be the subset of A containing only the constraints specified by a single positive literal, and let [Gamma]' = [Gamma] [union] {(0, 0)}. Let [Delta] be the subset of [Lambda] containing only the constraints specified by a single negative literal. Note that the set of constraints [Delta]*, constructed according to Definition 5, is equal to the set of constraints specified by arbitrary finite disjunctions of negative literals (including the empty disjunction).

Now it is easily shown that [Delta] is 1-independent with respect to [Gamma]' (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, [CSP.sub.[Delta][is less than or equal to] 1] ([Gamma] [union] [Delta]*) is tractable, since each instance is specified by a conjunction of zero or more positive literals together with at most one negative literal. Hence, by Corollary 1, we conclude that [CSP.sub.[Delta][is less than or equal to] 1] is tractable. But [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is the set of constraints specified by a disjunction of literals containing at most one positive literal. Examples of such clauses include the following:

[x.sub.1] [disjunction] ?? [x.sub.2] [disjunction] ?? [x.sub.3]

[x.sub.2]

?? [x.sub.1] [disjunction] ?? [x.sub.2] [disjunction] ?? [x.sub.4] [disjunction] ?? [x.sub.5]

It is easy to see that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] corresponds exactly to the HORN-CLAUSE SATISFIABILITY problem [Garey and Johnson 1979]. The constraint relations defined by conjunctions of clauses of this form are precisely the elements of the third class of tractable Boolean relations identified by Schaefer [1978] (which he calls `weakly negative' relations).

By a symmetric argument, it follows that the set of constraints specified by a disjunction of literals containing at most one negative literal is also a tractable set of constraints. The constraint relations defined by conjunctions of clauses of this form are precisely the elements of the fourth class of tractable Boolean relations identified by 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 [Delta] is k-independent with respect to a set [Gamma], for some value of k larger than one, then this may not be sufficient to ensure tractability of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Example 8. In this example we construct two sets of constraints, [Gamma] and [Delta], such that [CSP.sub.[Delta][is less than or equal to] 2] ([Gamma] [union] [Delta]) is tractable, and [Delta] is 2-independent with respect to [Gamma], but [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is NP-complete.

Recall the set of unary Boolean constraints, [Lambda], defined in Example 4, which contains all constraints specified by a single literal. Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and [Delta] = [Lambda].

With these definitions, CSP([Gamma] [union] [Delta]) is equivalent to the standard 2-SATISFIABILITY problem, and hence [CSP.sub.[Delta][is less than or equal to] 2] ([Gamma] [union] [Delta]) is tractable. Furthermore, the 2-SATISFIABILITY problem has the property that `path-consistency' guarantees global consistency [Jeavons et al. 1998], which implies that any minimal insoluble subset of clauses in an instance of 2-SATISFIABILITY contains at most two single literals, and hence [Delta] is 2-independent with respect to [Gamma],

However, as discussed in Example 4, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] corresponds to the 3-SATISFIABILITY problem, and is therefore NP-complete.

3.3. THE KROM PROPERTY. In this section, we identify a final sufficient condition for constructing tractable disjunctive constraints.

Definition 10. A set of constraints, [Delta], has the Krom property if it is 2-independent with respect to the empty set.

Note that [Delta] has the Krom property if and only if for every finite C [subset or equal to] [Delta] having no solution, there exists a pair of (not necessarily distinct) constraints [c.sub.i], [c.sub.j] [element of] C such that {[c.sub.i], [c.sub.j]} has no solution.

The name "Krom property" is chosen to emphasize the close connection with Krom clauses (i.e., Boolean clauses of length [is less than or equal to] 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 finite set of constraints [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] has a solution.

FIG. 2. An algorithm for a function Krom-Solvable.

Krom-Solvable(C: FINITE SUBSET OF [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]) P := {[[Pi].sub.1](c) | c [element of] C} [union] {[[Pi].sub.2](c) | c [element of] C} DEFINE A SET OF BOOLEAN VARIABLES {[q.sub.c] | c [element of] P} A := {(?? [q.sub.c'] [disjunction] ?? [q.sub.c"]) | c', c" [element of] P AND Sol ({c',c"}) = 0} B:= {([q.sub.c'] [disjunction] [q.sub.c"]) | [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]c [element of] C, c' = [[Pi].sub.1](c), c" = [[Pi].sub.2](c)} IF A [union] B IS SATISFIABLE THEN RETURN TRUE ELSE RETURN FALSE

The next result shows that Krom-Solvable correctly determines whether or not a finite set of constraints chosen from [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] has a solution in all cases when [Delta] has the Krom property.

LEMMA 3. If C is a finite subset of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and [Delta] has the Krom property, then the function Krom-Solvable defined in Figure 2 correctly determines whether or not C has a solution.

PROOF. We show that the function Krom-Solvable defined 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, [micro], for A [union] B. Define the set of constraints C' [subset or equal to] [Delta] as follows:

C' = {c|[micro]([q.sub.c]) = TRUE}.

We first show that C' has a solution. Since [Delta] has the Krom property, C' has no solution only if there exist c', c" [element of] C' such that {c', c"} has no solution. However, this cannot happen because [micro] satisfies the formulae in the set A.

Now, let the function f be a solution of C'. For each constraint c [element of] C we know that at least one of [[Pi].sub.1](c) and [[Pi].sub.2](c) is a member of C', because [micro] satisfies the formulae in B. Since f is a solution of C', 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').

if: Assume that C has a solution and let f be any such solution. Define the truth assignment [micro]: {[q.sub.c]|c [element of] P} [right arrow] {TRUE, FALSE} as follows:

[micro]([q.sub.c]) = TRUE iff c is satisfied by f.

We show that [micro] is a satisfying truth assignment of A [union] B by considering the elements of A and B in turn.

(1) For each formula (?? [q.sub.c'] [disjunction] ?? [q.sub.c"]) [element of] A, we know that {c', c"} has no solutions. Hence it cannot be the case that [micro]([q.sub.c']) = [micro]([q.sub.c"]) = TRUE, which means that (?? [q.sub.c] [disjunction] ?? [q.sub.c']) is satisfied by [micro].

(2) For each formula ([q.sub.c'] [disjunction] [q.sub.c"]) [element of] B, we know that there is a constraint c [element of] C such that [[Pi].sub1](c) = c' and [[Pi].sub.2](c) = c". Since f is a solution to C, f satisfies either c, c', or both. Hence, la assigns TRUE to at least one of [q.sub.c'], [q.sub.c"], which means that ([q.sub.c'] [disjunction] [q.sub.c"]) is satisfied by [micro].

It follows that A [union] B is satisfiable, so Krom-Solvable returns TRUE. []

By analyzing the complexity of the algorithm in Figure 2, we now establish the following result:

THEOREM 3. For any set of constraints [Delta], if CSP([Delta]) is tractable, and [Delta] has the Krom property, then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is tractable.

PROOF. By Lemma 3, it is sufficient 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 finite subset of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and let l(C) be the length of the string specifying C.

Since computing [[Pi].sub.1] and [[Pi].sub.2] takes linear time, the set P can be computed in O(l(C)) time. It contains at most 2|C| elements.

To compute the set A, the algorithm must determine whether or not there is a solution to {c', c"} for every pair of constraints c', c" [element of] P. Since {c', c") is an instance of CSP([Delta]), 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(|C|2 [multiplied by] p(l(C))), for some polynomial p. The set A contains at most |C|(2|C| - 1) elements.

The set B can clearly be computed in time O(|C|l(C)) and contains |C| elements.

Finally, the algorithm must decide the satisfiability of a set of Krom clauses containing at most |C|(2|C| - 1) + |C| elements. By using the linear time algorithm for this problem given in Aspvall et al. [1979], this step can be carried out in O(|C|2) time.

Hence, the total time required by the algorithm is O(|C|2 [multiplied by] 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, A, defined in Example 4, which contains all constraints specified by a single literal.

It is easily shown that [Lambda] has the Krom property (since any collection of positive and negative literals has a solution unless it contains two different literals involving the same variable). Hence, by Theorem 3, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is tractable.

However, the set [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] contains all constraints specified by Boolean clauses containing at most two literals, that is, all Krom clauses.

The constraint relations defined by conjunctions of clauses of this form are precisely the elements of the fifth class of tractable Boolean relations identified by Schaefer [1978] (which he calls `bijunctive' relations).

To conclude this section, we show that if a set of constraints [Delta] has a higher level of k-independence with respect to the empty set, then this may not be sufficient to ensure tractability of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Example 10. In this example, we construct a tractable set of relations [Delta] such that [Delta] is 3-independent with respect to the empty set, but we show that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is NP-complete.

For all possible variables x and y, we define the unary constraints zero(x), one(x) and the binary constraint [is not equal to][sub.N] (x, y) as follows:

(1) zero(x) denotes the constraint ({x}, {f: {x} [right arrow] N|f(x) = 0});

(2) one(x) denotes the constraint ({x}, {f: {x} [right arrow] N|f(x) = 1});

(3) [is not equal to] [sub.N] (x, y) denotes the constraint ({x,y}, {f: {x, y} [right arrow] N|f(x) [is not equal to] f(y)}).

Define [Delta] to be the set containing all possible constraints of these three types. (Note that [Delta] is well defined since we are assuming that we have a fixed universe of possible variable names.)

Let C be a finite subset of [Delta]. 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.

S1 = {zero(x), one(x)}

S2 = {[[is not equal to] [.sub.N](x, x)}

S3 = {zero(x), zero(y), [[is not equal to] [.sub.N](x, y)}

S4 = {one(x), one(y), [[is not equal to] [.sub.N](x, 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 X = {[x.sub.2], ..., [x.sub.n]}. Define the function f: X [right arrow] N as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

For each constraint c [element of] C, we can reason as follows:

--Since S1 [is not a subset or equal to] C, if c equals zero ([x.sub.i]) or one([x.sub.i]), then f satisfies c.

--Since S2 [is not a subset or equal to] C, if c is the constraint [is not equal to] [.sub.N (x.sub.i], [x.sub.j) then i [is not equal to] j.

--Since neither S3 nor S4 is a subset of C, if c is the constraint [is not equal to] [.sub.N] (x.sub.i] [x.sub.j]) and i [is not equal to] j, then f([x.sub.i]) [is not equal to] f([x.sub.j]).

Hence, in all cases c is satisfied 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 [Delta] is 3-independent with respect to the empty set, and that [Delta] is tractable.

To establish the NP-completeness of CSP ([MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]), we construct a polynomial time reduction from the NP-complete problem 4-COLORABILITY [Garey and Johnson 1979], as follows.

Let G = (V, E) be an arbitrary graph and construct an instance of CSP ([MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]) as follows: for each v [element of] V, introduce two variables v' and v" Together with the constraints

--zero(v') [disjunction] one(v'); and

--zero(v") [disjunction] one(v").

For each edge (v, w) [element of] E, introduce the constraint

--[is not equal to] [sub.N] (v', w') [disjunction] [is not equal to] [.sub.N] (v", w").

This transformation can obviously be carried out in polynomial time and the resulting set of constraints is a subset of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

To see that the resulting instance has a solution if and only if the graph G is 4-colorable, identify color 1 with v' = 0, v" = 0, color 2 with v' = 0, v" = 1, and so on. For every pair of adjacent nodes v, w in G, the constraint imposed on the corresponding variables v', w', v", w" ensures that v and w must be assigned different colors.

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 defined in Definition 4. We will also describe some new tractable sets of constraints which have not previously been identified.

Example 11. [Max-closed constraints]. The class of constraints known as `max-closed' constraints was introduced in Jeavons 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 [Lesaint et al. 1998; Purvis and Jeavons 1999].

Max-closed constraints are defined in Jeavons and Cooper [1995] for arbitrary finite 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 finite set of natural numbers:

[3x.sub.1] + [x.sub.5] + [3x.sub.4] [is greater than or equal to] [2x.sub.2] + 10,

[4x.sub.1] [is not equal to] 8,

[x.sub.1] [element of] {1, 2, 3, 5, 7, 11, 13},

[2x.sub.1][x.sub.3][x.sub.5] [is greater than or equal to] [3x.sub.2] + 1,

([3x.sub.1] [is greater than or equal to] 7) [disjunction] ([2x.sub.1] [is greater than or equal to] 4) [disjunction] ([5x.sub.2] [is less than or equal to] 7).

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 generalize this result to obtain tractable constraints over infinite sets of values.

Max-closed constraints were originally defined 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 characterized as those constraints that can be specified by a conjunction of disjunctions of inequalities of the following form:

([x.sub.1] [is greater than] [a.sub.1]) [disjunction] ([x.sub.2] [is greater than] [a.sub.2]) [disjunction ?? [disjunction]([x.sub.r] [is greater than] [a.sub.r]) [disjunction] ([x.sub.j] [is less than] [a.sub.j])

In this expression, the [x.sub.i] are variables and the [a.sub.i] are constants.

To apply the results of Section 3.2, let the set of possible values, D, be any totally ordered set. Define [Gamma] to be the set of all constraints specified by a single inequality of the form [x.sub.i] [is less than] [a.sub.i], for some [a.sub.i] [element of] D, together with the empty constraint. Define [Delta] to be the set of all constraints specified by a single inequality of the form [x.sub.i] [is greater than] [a.sub.i] for some [a.sub.i] [element of] D. Note that the set of constraints [Delta]*, constructed as in Definition 5, is equal to the set of constraints specified by arbitrary finite disjunctions of inequalities of the form [x.sub.i] [is greater than] [a.sub.i].

It is easily shown that [Delta] is 1-independent with respect to [Gamma]. Also, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] ([Gamma] [union] [Delta] 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, [Gamma] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] [Delta]* 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 are tractable [Jeavons and Cooper 1995; Jeavons et al. 1995], the argument above can still be applied when the set of values D is infinite.

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, identified and shown to be tractable by 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 generalize this result to obtain tractable constraints over infinite sets of values.

Let the set of possible values D be the ordered set {[d.sub.1], [d.sub.2], ... , [d.sub.m]}, where [d.sub.1] [is less than] [d.sub.2] [is less than] [d.sub.m]. The definition of connected row-convex constraints given in Deville et al. [1.997] uses a standard matrix representation for binary relations: the binary relation R over D is represented by the m X m 0-1 matrix M, by setting [M.sub.ij] = 1 if the relation contains the pair ([d.sub.i], [d.sub.j]), and [M.sub.ij] = 0 otherwise.

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 relations:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

An alternative characterization of this class of constraints, in terms of an algebraic closure property was given in Jeavons et al. [1998].

Here, we obtain another alternative characterization by noting that the corresponding 0-1 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 submatrix 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 (conjunction) 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 different forms of such matrices, depending on which corner submatrix is zero, and they correspond to constraints expressed by disjunctive expressions of the four following forms:

([x.sub.i] [is greater than or equal to] [d.sub.i]) [disjunction] ([x.sub.j] [is greater than or equal to] [d.sub.j)

([x.sub.i] [is greater than or equal to] [d.sub.i]) [disjunction] ([x.sub.j] [is less than or equal to] [d.sub.j)

([x.sub.i] [is less than or equal to] [d.sub.i]) [disjunction] ([x.sub.j] [is greater than or equal to] [d.sub.j)

([x.sub.i] [is less than or equal to] [d.sub.i]) [disjunction] ([x.sub.j] [is less than or equal to] [d.sub.j)

In these expressions, [x.sub.i], [x.sub.j] are variables and [d.sub.i] [d.sub.j] are constants.

Finally, we note that a row or column consisting entirely of zeros corresponds to a constraint of the form ([x.sub.i] [is less than or equal to] [d.sub.1]) [disjunction] ([x.sub.i] [is greater than or equal to] [d.sub.2]) for an appropriate choice of [d.sub.1] and [d.sub.2].

Hence, any connected row-convex constraint is equivalent to a conjunction of expressions of these forms.

To apply the results of Section 3.3, define [Delta] to be the set of all unary constraints specified by a single inequality of the form [x.sub.i] [is less than or equal to] [d.sub.i] or [x.sub.i] [is greater than or equal to] [d.sub.i], for some [d.sub.i] [element of] D.

It is easily shown that [Delta] has the Krom property and CSP([Delta]) is tractable, since each instance consists of a conjunction of upper and lower bounds for individual variables. Hence, by Theorem 3, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is tractable. By the alternative characterization 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 infinite.

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] and Koubarakis [1996] and shown to be tractable.

A linear Horn constraint is specified 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:

[3x.sub.1] + [x.sub.5] - [3x.sub.4] [is less than or equal to] 10,

[x.sub.1] + [x.sub.3] + [x.sub.5] [is not equal to] 7,

([3x.sub.1] + [x.sub.5] - [4x.sub.3] [is less than or equal to] 7) [disjunction] ([2x.sub.1] + [3x.sub.2] - [4x.sub.3] [is not equal to] 4) [disjunction] ([x.sub.2] + [x.sub.3] + [x.sub.5] [is not equal to] 7),

([4x.sub.1] + [x.sub.3] [is not equal to] 3) [disjunction] ([5x.sub.2] - [3x.sub.5] + [x.sub.4] [is not equal to] 6).

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, 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). Define [Gamma] to be the set of all constraints specified by a single (weak) linear inequality (e.g., [3x.sub.1] + [2x.sub.2] - [x.sub.3] [is less than or equal to] 6), together with the empty constraint. Define [Delta] to be the set of all constraints specified by a single linear disequality (e.g., [x.sub.1] + [4x.sub.2] + [x.sub.3] [is not equal to] 0).

Note that [Delta]* is the set of constraints specified by a disjunction of disequalities, and the problem CSP([Gamma] [union] [Delta]*) corresponds to deciding whether a convex polyhedron, possibly minus the union of a finite number of hyperplanes, is the empty set. It was shown in Lassez and McAloon [1989] that the set [Gamma] [union] [Delta]* is independent (using 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 specified by linear Horn constraints corresponds to the much larger set [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and this set is not independent in the sense defined 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([Gamma] [union] [Delta]). Let C' = C [intersection] [Gamma] (the subset of C which is specified by weak linear inequalities), and let C" = C [intersection] [Delta] (the subset of C which is specified by linear disequalities). By considering the geometrical interpretation of the constraints as half spaces and excluded hyperplanes in [R.sup.n], it is clear that C is consistent if and only if C' is consistent, and, for each c [element of] C", the set C' [union] {c} is consistent (see Koubarakis [1996]). Hence, [Delta] is 1-independent with respect to [Gamma].

Now Lemma 2 and Lemma 1 imply that the function Ind-Solvable defined in Figure 1 can be used to determine whether [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] has a solution. (In fact, the algorithm in Figure 1 can be seen as a generalization of the algorithm CONSISTENCY, which was developed specifically for this problem in Koubarakis [1996].)

Finally, to establish tractability, we note that whether a set of inequalities, C', 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' [union] {c} is consistent by simply running Khachian's algorithm to determine whether C' implies the negation of c. Hence, [CSP.sub.[Delta][is less than or equal to] 1] ([Gamma] [union] [Delta]) is tractable, so can apply Corollary 1 and conclude that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is tractable.

Example 14. [Extended Horn clauses]. It was shown by Chandru and Hooker [1991] that the class of Horn clauses may be generalized 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 [1991] give a very indirect argument based on a result from the theory of linear programming. 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 define this new class of tractable constraint sets over Boolean variables, we first 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 infinite number of edges. If we select an edge of T, then it can be oriented in two different ways: either towards the root, or else away from the root. An edge of T, together with a particular selected orientation, will be called an arc of T.

For each possible arc, a, of T we define an associated literal, in the following way. If a is oriented away from the root, then we define the associated literal to be the label of a in T; otherwise, if a is oriented towards the root, then we define the associated literal to be the negation of the label of a in T.

For example, let T be the tree shown in Figure 3, with root node [n.sub.0]. and consider the arc from node [n.sub.0] to [n.sub.1] denoted [[n.sub.0], [n.sub.1]]. The literal associated with [[n.sub.0], [n.sub.1]], according to the definition just given, is x.sub.1]. Now consider the arc from node [n.sub.5] to [n.sub.2], denoted [[n.sub.5], [n.sub.2]]. The literal associated with [[n.sub.5], [n.sub.2]] is [[x.sub.6].

[Figure 3 ILLUSTRATION OMITTED]

Given any set of arcs, we define an associated clause consisting of the disjunction of the associated literals. For example, the clause associated with the set of arcs {[[n.sub.0], [n.sub.1]], [[n.sub.5], [n.sub.2]]} is [x.sub.1] [disjunction] [x.sub.6].

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.sub.0], [n.sub.1] and [[n.sub.1], n.sub.3]] form a path of length 2. The arcs [n.sub.6], n.sub.4]], [n.sub.4], [n.sub.1]], [[n.sub.1], [n.sub.0]] and [[n.sub.0], n.sub.2]] form a path of length 4.

For any rooted, undirected, tree T, we define [Gamma] [.sub.T] to be the set of all Boolean constraints specified by a clause associated with some path in T.

For example, when T is the tree shown in Figure 3, then [Gamma] [.sub.T] includes the clauses [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] but does not include the clause [x.sub.1] [disjunction] [x.sub.6], or the clause [x.sub.1] [disjunction] ??[x.sub.2].

We first note that for any tree T, including infinite trees, the set of constraints [Gamma] [.sub.T] is tractable. This is because any instance of CSP([Gamma] [.sub.T) can be solved by the following polynomial-time algorithm (adapted from Chandru and Hooker [19911):

(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 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 satisfied 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 [Gamma] [.sub.T] then we no longer have tractability. In fact, we will now show that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] can be NP-complete.

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). Define [S.sub.n] to be a star with n edges labelled [x.sub.1], [x.sub.2], ..., [x.sub.n. For example, the star [S.sub.5] is shown in Figure 4. Now consider the infinite star, [S.sub.[infinity]] with edges labelled [x.sub.1], [x.sub.2],.... The set of constraints [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] consists of all constraints specified by clauses of the form [x.sub.i], ??[x.sub.i], or [x.sub.i] [disjunction] ??[x.sub.j], for all choices of i and j. Hence, the class of constraints [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] consists of all constraints specified by disjunctions of these clauses, or, in other words, by clauses of the form [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for all possible choices of i, j, k, l. This set of clauses does not fall into any of the 6 tractable classes identified by Schaefer [1978], and hence the corresponding satisfiability problem, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], is NP-complete.

In order to obtain tractable sets of disjunctive constraints, we now identify a restricted subset of [Gamma] [.sub.T] that is 1-independent with respect to [Gamma] [.sub.T].

For any rooted, undirected, tree T, we define [Delta] [.sub.T] to be the set of all Boolean constraints specified 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 [Delta] [.sub.] includes the clauses ??[x.sub.2] [disjunction] ??[x.sub.1], [x.sub.4] [disjunction] ??[x.sub.3] [disjunction] ??[x.sub.1], and ??[x.sub.5], but does not include the clause [x.sub.4] [disjunction] ??[x.sub.3], or the clause ??[x.sub.5] [disjunction] [x.sub.1]. As a second example, when T is a star labelled with positive literals, such as the one shown in Figure 4, then [Delta] [.sub.T] consists of all constraints specified by a single negative literal.

[Figure 4 ILLUSTRATION OMITTED]

Since [Delta] [.sub.T] [subset or equal to] [Gamma] [.sub.T], we can use the same algorithm as before to show that the problem [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is tractable. To show that [Delta] [.sub.T] is 1-independent with respect to [Gamma] [.sub.T], we note that any minimal incompatible subset of clauses can involve at most one clause from [Delta] [.sub.T]. In view of these facts, we can apply Corollary 1 to conclude that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is tractable.

Notice that in the special case when T is a star labelled with positive literals the set of constraints [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] 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 [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] includes the extended Horn set of clauses associated with T, as defined by Chandru and Hooker [1991]. Furthermore, in the most general case when T is an arbitrary tree labelled with arbitrary literals, the set of constraints [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] includes the hidden extended Horn clauses associated with T, as defined by Chandru and Hooker [1991]. Hence, our results are sufficient 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 defined in Chandru and Hooker [1991], is a little more restricted than the set of constraints [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and hence our result represents a generalization 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 [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] form 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 [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] includes the clause ??[x.sub.1] [disjunction] ??[x.sub.2] [disjunction] ??[x.sub.3] [disjunction] [x.sub.6] (formed from the disjunction of ??[x.sub.1] [disjunction] ??[x.sub.2] and ??[x.sub.1] [disjunction] ??[x.sub.3] and [x.sub.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 literals in such a way that each variable name appears at most once. Note that T may have an infinite number of edges. We define [Delta] [.sub.T] to be the set of all Boolean constraints specified 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, the [Delta.sub.T] includes the clauses ??[x.sub.2] [disjunction] ??[x.sub.1], [x.sub.1] [disjunction] [x.sub.2], and ??[x.sub.5], but does not include the clause [x.sub.4] [disjunction] ??[x.sub.3], or the clause ??[x.sub.5] [disjunction] [x.sub.1]. As a second example, when T is a star labelled with positive literals, such as the one shown in Figure 4, then [Delta.sub.T] consists of all constraints specified by a single positive or negative literal.

The algorithm described in Example 14 can be used to show that CSP([Delta.sub.T]) is tractable. Furthermore, it is easy to show that any set of clauses chosen from [Delta.sub.T] is satisfiable, unless it contains the unit clauses [x.sup.i] and ??[x.sub.i] for some i. Hence [Delta.sub.T] has the Krom property. In view of these facts, we can apply Theorem 3 to conclude that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is tractable.

Notice that in the special case when T is a star the set of constraints [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] 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 [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] includes a wider variety of clauses. For example, when T is the tree shown in Figure 3, then [Delta.sub.T] includes the following clauses:

[x.sub.1] [disjunction] [x.sub.2] [disjunction] [x.sub.3]

??[x.sub.2] [disjunction] ??[x.sub.1][disjunction][x.sub.5] [disjunction] ??[x.sub.6]

??[x.sub.1] [disjunction] ??[x.sub.5]

Example 16. [Tractable set constraints]. In Drakengren and Jonsson [1998; 1997], Drakengren and Jonsson identify a number of tractable classes of set constraints that are specified by expressions involving set-valued variables and the relation symbols [subset or equal to], disj (denoting disjointness) and [subset or equal to]

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 first give the relevant definitions from Drakengren and Jonsson [1998; 1997]. An atomic set constraint or atomic set relation is an expression of the form [x.sub.i] [subset or equal to] [x.sub.j], [x.sub.i] [x.sub.i] [is not equal to] [x.sub.j]. A 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.sub.1] [is not equal to] [x.sub.j] or [x.sub.i] disj [x.sub.j] and at most one disjunct of the form [x.sub.i] [subset or equal to] [x.sub.j]. A DSR is called 2-Horn if it consists of zero or more disjuncts of the form [x.sub.i] [subset or equal to] [x.sub.j] and at most one disjunct of the form [x.sub.i] [subset or equal to] [x.sub.j] or [x.sub.i] disj [x.sub.i]. The following are examples of Horn DSRs.

([x.sub.1] [subset or equal to] [x.sub.2]) [disjunction] ([x.sub.3] [is not equal to] [x.sub.4]) [disjunction] ([x.sub.4] [subset or equal to]) [disjunction] ([x.sub.5] disj [x.sub.7])

(x.sub.1] [subset or equal to] [x.sub.2]) [disjunction] ([x.sub.3] [subset or equal to] [x.sub.4]) [disjunction] ([x.sub.4] [is not equal to] [x.sub.7])

([x.sub.5] disj [x.sub.7]) [disjunction] ([x.sub.3] [is not equal to] [x.sub.4]) [disjunction] ([x.sub.4] [is not equal to] [x.sub.7])

The latter two examples in this list are also 2-Horn.

An [S.sub.0]-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 set variables to nonempty sets. An atomic constraint [x.sub.1] R [x.sub.2] is satisfied by an [S.sub.0]-interpretation (S-interpretation), I, if and only if I([x.sub.1]) R I([x.sub.2]). A DSR d = [d.sub.1] v ... v [d.sub.n] is [S.sub.0]-satisfiable (S-satisfiable) if there exists an S??-interpretation (S-interpretation) which satisfies some disjunct [d.sub.i] of d. A set C of DSRs is [S.sub.0]-satisfiable (S-satisfiable) if there exists an [S.sub.0]-interpretation (S-interpretation) which satisfies all members of C. Such a satisfying [S.sub.0]-interpretation (S-interpretation) is called an [S.sub.0]-model (S-model) of C.

The following decision problems are studied in Drakengren and Jonsson [1998; 1997]:

--[HORNDSRSAT.sub.0]: Instance: A finite set C of Horn DSRs. Question: Does there exist an [S.sub.0]-model of C?

--HORNDSRSAT: Instance: A finite set C of Horn DSRs. Question: Does there exist an S-model of C?

--[2HORNDSRSAT.sub.0]: Instance: A finite set C of 2-Horn DSRs. Question: Does there exist an [S.sub.0]-model of C?

--2HORNDSRSAT: Instance: A finite set C of 2-Horn DSRs. Question: Does there exist an S-model of C?

The problem [HORNDSRSAT.sub.0] is NP-complete [Drakengren and Jonsson 1998]. To show that the problem HORNDSRSAT can be solved in polynomial time we define [Gamma] to be the set of all constraints specified by expressions of the form x [subset or equal to] y (where x and y are set-valued variables that must be assigned nonempty sets), together with the empty constraint. We define [Delta] to be the set of all constraints specified by expressions of the form x [is not equal to] 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 [Delta]* is the set of all constraints specified by arbitrary disjunctions of expressions of the form x [is not equal to] 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 [subset or equal to] x, z [subset or equal to] y and x dis] y are implied by the given constraint set, the input set is rejected (because variable z is forced to be equal to ??). Second, if there is a pair of set variables x and y for which the constraints x [subset or equal to] y, y [subset or equal to] x and x [is not equal to] y are implied by the given constraint set, then the input is rejected (because these constraints cannot all be satisfied). If a constraint set passes both of these tests, then it is accepted.

The existence of this simple algorithm implies that CSP([Gamma] [union] [Delta]) and hence also [CSP.sub.[Delta][is less than or equal to] 1] ([Gamma] [union] [Delta]) can be solved in polynomial time. It also implies that [Delta] is 1-independent with respect to [Gamma]. Hence, by Corollary 1, we can immediately conclude that CSP([MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]), which corresponds to the decision problem HORNDSRSAT, can be solved in polynomial time. In fact, the algorithm defined in Figure 1 can be seen as a generalization 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.sub.0] can be solved in polynomial time, define [Gamma] to be the set of all constraints specified by an expression which is either of the form x [subset or equal to] 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. Define [Delta] to be the set of all constraints specified by an expression of the form x [is not equal to] y (where x and y are set-valued variables which can be assigned arbitrary sets), together with the empty constraint. In this case, [Delta]* is the set of constraints specified by a disjunction of expressions of the form x [is not equal to] y.

In Drakengren and Jonsson [1998], it is shown that the problem of deciding whether a set of atomic set constraints has an [S.sub.0]-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 [subset or equal] to x, z [subset or equal] 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 find out whether a contradictory triple of constraints x [subset or equal] y, y [subset or equal] x and x [is not equal to] y is 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([Gamma] [union] [Delta]) and hence also [CSP.sub.[Delta][is less than or equal to] 1] ([Gamma] [union] [Delta]) can be solved in polynomial time. It also implies that [Delta] is 1-independent with respect to [Gamma]. Hence, by Corollary 1, we can immediately conclude that CSP([MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]), which now corresponds to the decision problem 2HORNDSRSAT?? can be solved in polynomial time. As in the above case, the algorithm defined in Figure 1 can be seen as a generalization of the iterative version of Algorithm 2-Horn-Sat presented in Drakengren and Jonsson [1998].

Having identified 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 that 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 [equivalent] [a.sub.1] (mod[m.sub.1])

x [equivalent] [a.sub.2] ([mod[m.sub.2]) ...

x [equivalent] [a.sub.n] (mod[m.sub.n])

is solvable if and only if the greatest common divisor of [m.sub.i] and [m.sub.j] divides [a.sub.i] - [a.sub.j], 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. Define [Gamma] to be the set of all unary constraints which are specified by a linear congruence of the form x [equivalent] a (mod m), for some natural number a, and some modulus m, together with the empty constraint. For each natural number b, define [[Gamma].sub.b] to be the subset of [Gamma] containing all unary constraints which are specified by a congruence of the form x [equivalent] b (mod m), for some m.

A problem instance in CSP([Gamma]) is specified by a collection of simultaneous congruences. For example, a typical set of constraints in CSP([Gamma]), involving the variables [x.sub.1] and [x.sub.2], would be:

[x.sub.1] [equivalent] 3 (mod 5),

[x.sub.2] [equivalent] 4 (mod 6),

[x.sub.2] [equivalent] 2 (mod 4).

The Chinese Remainder Theorem implies that any set of constraints in CSP([Gamma]) 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 definition of compatibility above that every pair of constraints in [[Gamma].sub.b] is compatible. Hence, [[Gamma].sub.b] has the guaranteed satisfaction property, and by Theorem 1 we conclude that CSP([MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]) is tractable. This means that there is an efficient way to solve any collection of simultaneous disjunctions of congruences which all have the property that at least one disjunct comes from [[Gamma].sub.b]. For example, when b = 2 we might have the following collection:

[x.sub.1] [equivalent] 2 (mod 4) [disjunction] [x.sub.1] [equivalent] 2 (mod 3) [disjunction] [x.sub.2] [equivalent] 1 (mod 5),

[x.sub.2] [equivalent] 2 (mod 3) [disjunction] [x.sub.3] [equivalent] 2 (mod5),

[x.sub.3] [equivalent] 2 (mod 7),

[x.sub.2] [equivalent] 2 (mod 7) [disjunction] [x.sub.1] [equivalent] 3 (mod 12) [disjunction] [x.sub.3] [equivalent] 1 (mod 3)

--For any natural number b, [CSP.sub.[Gamma]b [is less than or equal to] 1]([Gamma] [union] [[Gamma].sub.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. Furthermore, no pair of constraints which are both in [[Gamma].sub.b] can be incompatible, so [[Gamma].sub.b] is 1-independent with respect to [Gamma]. Hence, by Corollary 1, we conclude that CSP([MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]) is also tractable, for any natural number b. This means that there is an efficient way to solve any collection of simultaneous disjunctions of congruences which all have the property that at most one disjunct comes from [Gamma] and the remainder (if any) from [[Gamma].sub.b]. For example, when b = 2, we might have the following collection of congruences:

[x.sub.1] [equivalent] 1 (mod 4) [disjunction] [x.sub.1] [equivalent] 2 (mod 3) [disjunction] [x.sub.2] [equivalent] 2 (mod 5),

[x.sub.2] [equivalent] 2 (mod 3) [disjunction] [x.sub.3] [equivalent] 2 (mod 5),

[x.sub.3] [equivalent] 5 (mod 7),

[x.sub.2] [equivalent] 1 (mod 7) [disjunction] [x.sub.3] [equivalent] 2 (mod 12) [disjunction] [x.sub.3] [equivalent] 2 (mod 3)

--From the observations already made, it is clear that the set [Gamma] has the Krom property. Hence, by Theorem 3, we conclude that CSP([MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]) is tractable. This means that there is an efficient 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:

[x.sub.1] [equivalent] 1 (mod 4) [disjunction] [x.sub.1] [equivalent] 0 (mod 3),

[x.sub.2] [equivalent] 2 (mod 3) [disjunction] [x.sub.3] [equivalent] 2 (mod 5),

[x.sub.3] [equivalent] 5 (mod 7),

[x.sub.2] [equivalent] 1 (mod 7) [disjunction] [x.sub.1] [equivalent] 2 (mod 12)

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 sufficient conditions for tractability of disjunctive constraints. We have shown that these conditions account for a wide variety of known tractable constraint classes, over both finite and infinite 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 generalization of max-closed constraints to infinite (ordered) domains (Example 11);

--A generalization of connected row-convex constraints to infinite (ordered) domains (Example 12);

--A (slight) generalization 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 first 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 generality, 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.

An earlier version of some parts of this paper was presented at the International Conference on Constraint Programming in 1997 (see Cohen et al. [1997]).

Authors' addresses: D. Cohen, Department of Computer Science, Royal Holloway, University of London, Egham Hill, Egham, Surrey TW20 0EX, United Kingdom; P. Jeavons, Oxford University Computing Laboratory, Wolfson Building, Parks Road, OX1 3QD UK; P. Jonsson, Department of Computer and Information Science, Linkopings Universitet, S-581 83, Linkoping, Sweden; M. Koubarakis, Department of Electronic and Computer Engineering, Technical University of Crete, University Campus--Kounoupidiana, 73100 Crete, Greece.

Permission to make digital/hard copy of part or all of this work for personal or classroom use is granted without fee provided that the copies are not made or distributed for profit or commercial advantage, the copyright notice, the title of the publication, and its date appear, and notice is given that copying is by permission of the Association for Computing Machinery (ACM), Inc. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee.

REFERENCES

ASPVALL, B., PLASS, M., AND TARJAN, R. 1979. A linear time algorithm for testing the truth of certain quantified Boolean formulas. Inf. Proc. Lett. 8, 1121-123.

BERTINO, E., BETTINI, C., FERRARI, E., AND SAMARATI, P. 1998. An access control model supporting periodicity constraints and temporal reasoning. ACM Trans. Datab. Syst. 23, 3, 231-285.

CHANDRU, V., AND HOOKER, J. 1991. Extended Horn sets in propositional logic. J. ACM 38, 1 (Jan.), 205-221.

COHEN, D., JEAVONS, P., AND KOUBARAKIS, M. 1997. Tractable disjunctive constraints. In Proceedings of the 3rd International Conference on Constraint Programming--CP'97 (Linz, Austria, October). Lecture Notes in Computer Science, vol. 1330. Springer-Verlag, New York, pp. 478-490.

COOPER, M., COHEN, D., AND JEAVONS, P. 1994. Characterising tractable constraints. Artif. Int. 65, 347-361.

DECHTER, R., AND PEARL, J. 1989. Tree clustering for constraint networks. Artif. Int. 38, 353-366. DENENBERG, H., AND LEWIS, H.R. 1984. The complexity of the satisfiability problem for Krom formulas. Theoret. Comput. Sci. 30, 319-341.

DEVILLE, Y., BARETTE, O., AND VAN HENTENRYCK, P. 1997. Constraint satisfaction over connected row convex constraints. In Proceedings of International Joint Conference on Artificial Intelligence (IJCAI'97). pp. 405-411.

DRAKENGREN, T. 1997. Algorithms and Complexity for Temporal and Spatial Formalisms. Ph.D. dissertation. Dept. of Computer and Information Science, Linkoping University. Available from http://www.ida.liu.se/ext/pur/tphd/0498.html.

DRAKENGREN, T., AND JONSSON, P. 1997. Qualitative reasoning about sets applied to spatial reasoning. (Paper #7 in [Drakengren 1997]).

DRAKENGREN, T., AND JONSSON, P. 1998. Reasoning about set constraints applied to tractable inference in intuitionistic logic. J. Logic Comput. 8, 855-875.

FREUDER, E.C. 1985. A sufficient condition for backtrack-bounded search. J. ACM 32, 4 (Oct.), 755-761.

GAREY, M., AND JOHNSON, D. 1979. Computers and intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco, Calif.

GYSSENS, M., JEAVONS, P., AND COHEN, D. 1994. Decomposing constraint satisfaction problems using database techniques. Artif Int. 66, 1, 57-89.

JACKSON, T. 1975. Number Theory. Routledge and Kegan Paul.

JEAVONS, P., COHEN, D., AND COOPER, M. 1998. Constraints, consistency and closure. Artif. Int. 101, 1-2, 251-265.

JEAVONS, P., COHEN, D., AND GYSSENS, M. 1995. A unifying framework for tractable constraints. In Proceedings of the 1st International Conference on Constraint Programming--CP'95 (Cassis, France, September). Lecture Notes in Computer Science, vol. 976. Springer-Verlag, New York, pp. 276-291.

JEAVONS, P., COHEN, D., AND GYSSENS, M. 1997. Closure properties of constraints. J. ACM 44, 4 (July), 527-548.

JEAVONS, P., AND COOPER, M. 1995. Tractable constraints on ordered domains. Artif Int. 79, 2, 327-339.

JONSSON, P., AND BACKSTROM, C. 1998. A unifying approach to temporal constraint reasoning. Artif Int. 102, 143-155.

KABANZA, F., STEVENNE, J.-M., AND WOLPER, P. 1995. Handling infinite temporal data. J. Comput. Syst. Sci. 51, 3-17.

KHACHIAN, L. 1979. A polynomial rime algorithm for linear programming. Soviet Math. Dokl. 20, 191-194.

KIROUSIS, L. 1993. Fast parallel constraint satisfaction. Artif. Int. 64, 147-160.

KOUBARAKIS, M. 1992. Dense time and temporal constraints with [is not equal to]. In Principles of Knowledge Representation and Reasoning: Proceedings of the 3rd International Conference (KR'92) (San Mateo, Calif.), B. Nebel, C. Rich, and W. Swartout, eds., Morgan-Kaufmann, San Francisco, Calif., pp. 24-35.

KOUBARAKIS, M. 1995. From local to global consistency in temporal constraint networks. In Proceedings of the 1st International Conference on Constraint Programming--CP'95 (Cassis, France, September). Lecture Notes in Computer Science, vol. 976. Springer-Verlag, New York, pp. 53-69.

KOUBARAKIS, M. 1996. Tractable disjunctions of linear constraints. In Proceedings of the 2nd International Conference on Constraint Programming--CP'96 (Boston, Mass., Aug.). Lecture Notes in Computer Science, vol. 1118. Springer-Verlag, New York, pp. 297-307.

LASSEZ, J.-L., AND MCALOON, K. 1989. A canonical form for generalized linear constraints. In TAPSOFT'89, Advanced Seminar on Foundations of Innovative Software Development, Lecture Notes in Computer Science, vol. 351. Springer-Verlag, New York, pp. 19-27.

LASSEZ, J.-L., AND MCALOON, K. 1991. A constraint sequent calculus. In Constraint Logic Programming, Selected Research. MIT Press, Cambridge, Mass., pp. 33-43.

LASSEZ, J.-L., AND MCALOON, K. 1992. A canonical form for generalized linear constraints. J. Symb. Comput. 13, 1-24.

LESAINT, D., AZARMI, N., LAITHWAITE, R., AND WALKER, P. 1998. Engineering dynamic scheduler for work manager. BT Tech. J. 16, 16-29.

MACKWORTH, A. 1977. Consistency in networks of relations. Artif Int. 8, 99-118.

MONTANARI, U. 1974. Networks of constraints: Fundamental properties and applications to picture processing. Inf. Sci. 7, 95-132.

NEBEL, B., AND BURCKERT, H.-J. 1995. Reasoning about temporal relations: A maximal tractable subclass of Allen's interval algebra. J. ACM 42, 1 (Jan), 43-66.

PURVIS, L., AND JEAVONS, P. 1999. Constraint tractability theory and its application to the product development process for a constraint-based scheduler. In Proceedings of the 1st International Conference on the Practical Applications of Constraint Technologies and Logic Programming -- PACLP'99. pp. 63-79.

SCHAEFER, T. 1978. The complexity of satisfiability problems. In Proceedings of the 10th ACM Symposium on Theory of Computing (STOC) (San Diego, Calif., May 1-3). ACM, New York, pp. 216-226.

VAN BEEK, P., AND DECHTER, R. 1995. On the minimality and decomposability of row-convex constraint networks. Journal of the ACM 42, 3 (May), 543-561.

VAN HENTENRYCK, P., DEVILLE, Y., AND TENG, C.-M. 1992. A generic arc-consistency algorithm and its specializations. Artif. Int. 57, 291-321.

VILAIN, M., KAUTZ, H., AND VAN BEEK, P. 1989. Constraint propagation algorithms for temporal reasoning: A revised report. In Readings in Qualitative Reasoning about Physical Systems, D. Weld and J. de Kleer, eds., Morgan-Kaufmann, San Francisco, Calif., pp. 373-281.

VON ZUR GATHEN, J., AND GERHARD, J. 1999. Modern Computer Algebra. Cambridge University Press, Cambridge, England.

DAVID COHEN

Royal Holloway, University of London, London, United Kingdom

PETER JEAVONS

University of Oxford, Oxford, United Kingdom

PETER JONSSON

Linkopings Universitet, Linkoping, Sweden

MANOLIS KOUBARAKIS

Technical University of Crete, Crete, Greece

Printer friendly Cite/link Email Feedback | |

Author: | COHEN, DAVID; JEAVONS, PETER; JONSSON, PETER; KOUBARAKIS, MANOLIS |
---|---|

Publication: | Journal of the Association for Computing Machinery |

Date: | Sep 1, 2000 |

Words: | 15313 |

Previous Article: | A Bill of Rights and Responsibilities. |

Next Article: | A Neuroidal Architecture for Cognitive Computation. |

Topics: |