Amalgams of Constraint Satisfaction Problems

1 Introduction

In the Constraint Satisfaction Problem (CSP) the aim is to find an assignment to a set of variables subject specified con­ straints. CSP provides a generic approach to various com­ binatorial problems frequently appearing in artificial intelli­ gence and computer science, including the propositional sat­ isfiability problem, in which the variables must be assigned Boolean values, graph-theoretical problems, scheduling prob­ lems, temporal and spatial reasoning, database theory, and many others.

The general CSP is NP-complete [Montanari, 1974]. How­ ever, the time complexity of many practical problems can be considerably decreased by representing a problem as a com­ bination of smaller problems. Such decomposition methods have been intensively studied and implemented in most of ex­ isting constraint solvers. Most of them deals with the hyper­ graph associated with a problem instance (see, e.g. [Gottlob et al., 2000; Dechter and Pearl, 1989; Freuder, 1990]), and to date are highly developed. Another possibility, decompo­ sition of constraints themselves [Cohen et al., 1997; 2000b;

Eugeny S. Skvortsov

Ural State University, Ekaterinburg, Russia Skvortsov@dc.ru

2000a], remains almost uninvestigated. The present paper fo­ cuses on this class of decomposition methods.

In many cases of interest we may restrict the form of al­ lowed constraints by specifying a constraint language, that is a set of allowed constraints. Every constraint is specified by a relation, so, a constraint language is just a set of relations over the set of values. One of the most natural ways to decompose such a restricted CSP is to represent every its constraint as a disjunction of two or more simpler constraints on, possibly, smaller sets of values. We say that a constraint language, r, is the amalgam of r 1, r 2 if every constraint in r is the dis­ junction of a constraint from r 1 and a constraint from r 2 . In this case we call r 1, r 2 the components of r.

The main research direction in the study of amalgams is, of course, developing efficient algorithms solving the corre­ sponding constraint satisfaction problem. However, as we shall see the complexity of the CSP arising from an amalgam is not determined automatically by the complexity of its com­ ponents. Therefore, the first research problem we deal with is the tractability problem: under which conditions the problem arising from an amalgam is tractable. (A problem is called tractable if it can be solved in polynomial time.) Then we tackle the algorithmic problem: design efficient algorithms for tractable amalgams.

As is naturally expected, algorithms for amalgams tend to use algorithms for their components, especially if ones are already known. Unfortunately, in general, the connection be­ tween constraint languages and their amalgam cannot be ex­ pressed by usual constraint techniques, and strongly depends on properties of particular constraint languages. Thus, solu­ tions to both research problems are expected to be nontrivial.

Amalgams have been introduced in [Cohen et al., 1997], though another name was used. In [Cohen et a/., 2000a], amalgams were considered in the simplest case when the sets of values for languages r 1, r 2 are disjoint. In this case, for any amalgam, the corresponding problem is trivially re­ ducible to the problems over the components, that solves both the algorithmic problem and the tractability problem: an amalgam gives rise to a tractable problem if and only its components do. Certain properties of interaction of con­ straint languages may yield a reduction of an amalgam to its components. In [Cohen eta/., 1997] and later in [Cohen et al., 2000b], several such properties, so-called independence of constraint languages, have been identified. A number of previously unknown tractable constraint languages have been represented as amalgams of very simple and well studied in­ dependent constraint languages.

It has been shown in [Jeavons, 1998b] that the tractabil­ ity of the constraint satisfaction problem arising from a con­ straint language implies the tractability of the problem for the relational clone generated by the language. Therefore, a rea­ sonable strategy is to concentrate on relational clones rather than arbitrary constraint languages. In this paper we solve the tractability and algorithmic problems for amalgams of re­ lational clones. We completely characterise tractable amal­ gams and provide efficient algorithms in this case. The char­ acterisation criteria is stated in terms of, first, properties of components of an amalgam, and second, the tractability of a certain constraint language on a 2-element set of values. The latter language reflects the interaction of the components. Thus, both the characterisation and the reducing algorithms use Schaefer's Dichotomy Theorem for Boolean constraints [Schaefer, 1978].

Throughout the paper we heavily use the algebraic tech­ nique for CSP developed in [Jeavons, 1998b; Jeavons et al., 1998].

2 Preliminaries

2.1 Basic Definitions

Let A be a finite set. The set of all n-tuples of elements of A is denoted An. A subset of An is called an n-ary relation on A, and any set of finitary relations on A is called a constraint language on A.

Definition 1 Let r be a constraint language on a set A. CSP(r) is the combinatorial decision problem whose in­ stance is a triple P = (V; A; C) in which V is a set of vari­ ables, and C is a set of constraints, that is pairs of the form C = (s, {}) where sis a list of variables of length me, called the constraint scope, and{} E r is an mc-ary relation, called the constraint relation. The question is whether there exists a solution toP, that is a mapping <p: V --+ A such that <p( s) E {} for all (s, {}) E C.

Example 1 An instance of GRAPH q-COLORABILITY con­ sists of a graph G. The question is whether the vertices of G can be labelled with q colours so that adjacent vertices are assigned different colours.

This problem corresponds to CSP ( { =J A}) where A is a q­ element set (of colours) and =JA = {(a, b) E A 2 I a =J b} is the disequality relation on A.

A constraint language r is said to be tractable [NP-complete] if the problem CSP(r) is tractable [NP-complete] .

Now we introduce the central notion of the paper.

Definition 2 Let r A,r B be constraint languages on sets A, B respectively. The amalgam of r A' r B is defined to be the constraint language on A U B

Example2 Let A = {a,c,d},B = {b,c, d}, and rA = {{}A}, f B = {{}B} Where {}A, {}B are partial orders:

Columns of the matrices represent tuples of the relations. Then r A 1>4 r B = {{}Au {}B} where {}Au {}B is a quasiorder. Example 3 ([Cohen et al., 2000b]) Let Z be the set of all integers, and r the set of congruences of the form x = a (mod m) treated as unary relations. The Chinese Remainder Theorem implies that r is tractable. The amalgam r 1>4 r con­ sists of expressions of the form x = a (mod m) V x = b (mod n), and by results of [Cohen et al., 2000b] is tractable. For example, this means that we are able to recognised in polynomial time the consistency of the system

We are concerned with the following two problems.

Problem 1 (tractability problem) When is CSP(f1 1>4 f 2 ) tractable?

Problem 2 (algorithmic problem) Find a polynomial time algorithm for tractable CSP(f1 1>4 f 2 ).

In fact, properties of the amalgam do not strongly depend nei­ ther on properties of the original constraint languages nor on the way they interact. For example, if r 1 , r 2 contains no re­ lations of the same arity then their amalgam is empty. We, therefore, should restrict the class of constraint languages to be studied.

2.2 Relational Clones

For any problem in CSP(r), there may be some sets of variables whose possible values subject to certain constraints which are not elements of r. These constraints are said to be implicit and arise from interaction of constraints specified in the problem [Jeavons, 1998al.

To describe implicit constraint relations we make use of the natural correspondence between relations and predicates: for an n-ary relation {} on a set A, the n-ary predicate Pe is true on a tuple a if and only if a E (}. Usually, we will not distinguish a relation and the corresponding predicate, and freely use both terminology. An existential first order formula :ly1, ... , Ym<I>(xl, ... , Xn, YI, ... , Ym) is said to be primitive positive (pp-) if its quantifier-free part <I> is a conjunction of atomic formulas .

Definition 3 A relation is an implicit relation of a constraint language r on a set A if it can be expressed by a pp-formula involving relations from f and the equality relation =A·

A constraint language r is said to be a relational clone if it contains all its implicit constraint relations.

The relational clone (f) of all implicit constraint relations off is called the relational clone generated by r.

Example 4 The intersection of relations of the same arity, and Cartesian product are expressible via pp-formulas:

• Let {} be n-ary, and CJ m-ary relations. Then Pe xu Pe(XI , ... , Xn) 1\ P,.(Xn+I, ... , Xn+m)·

The notion of a relational clone considerably simplifies the analysis of constraint satisfaction problems in view of the following result that links the complexity of a constraint lan­ guage and the relational clone it generates.

Theorem 1 ([Jeavons, 1998b]) Let r be a constraint lan­ guage on a finite set, and r' <;;; (r) finite. Then CSP(f') is polynomial time reducible to CSP(r).

This result motivates restricting Problems I ,2 to the class of relational clones.

Example 3 (continuation) Reconsider the constraint lan­ guage r from Example 3. Results of [Cohen et at., 2000b] implies that (f) iXl (f) is also tractable. This larger amal­ gam includes, e.g., constraints of the form x =a (mod m)V y = b (mod n), which are not members of r iXl r.

2.3 Invariance Properties of Constraints

Another advantage of considering relational clones is that they often admit a concise description in terms of algebraic invariance properties [Poschel and Kaluznin, 1979; Jeavons, 1998b]. An (m-ary) operation f on a set A preserves an n-ary relation e on A (or e is invariant under f, or f is a polymorphism of e) if for any (au, . .. , anl), .. . , (alm, ... , anm) E e the tuple (!(au, ... ' alm), ... 'f(anl, ... 'anm)) belongs to e. For a given set of operations, C, the set of all relations invariant under every operation from Cis denoted by lnv C. Conversely, for a set of relations, r, the set of all operations preserving every relation from r is denoted by Pol r. Ev­ ery relational clone can be represented in the form lnv C for a certain set of operations C [Poschel and Kaluznin, 1979]. Therefore, in view of Theorem 1 the complexity of a finite constraint language depends only on its polymorphisms.

We need operations of some particular types that give rise to tractable problem classes.

Definition 4 Let A be a finite set. An operation f on A is called

• a constant operation if there is c E A such that f(xl , . . . , Xn) = c,for any X1, .. . , Xn E A;
• a semilattice operation 1 , if it is binary and satisfies the following three conditions: (a) f(x , x) = x, (b) f(x, f(y, z)) = f(f(x , y), z), (c) f(x , y) = f(y, x), foranyx,y,z E A;
• a majority operation if it is ternary, and f(x,x,y) f(x,y,x) = f(y,x,x) = x,foranyx,y E A;
• affineiff(x,y,z) = x-y+z,foranyx,y,z E A, where+,- are the operations of an Abelian group.

Proposition 1 ([Jeavons et al., 1998; 1997]) If r is a con­ straint language on a finite set, and Pol r contains an op­ eration of one of the following types: constant, semilattice, affine, majority; then r is tractable.

The complexity of constraint languages on a 2-element set is completely characterised in [Schaefer, 1978]. This outstand­ ing result is known as Schaefer's Dichotomy Theorem. By making use of Proposition 1 the algebraic version of Schae­ fer's theorem can be derived [Jeavons et at., 1997].

1 Note that in some earlier papers [Jeavons, 1998b; Jeavons et al., 1998] the term ACI operation is used.

Theorem 2 (Schaefer, [Schaefer, 1978]) A constraint lan­ guage r on a 2-element set is tractable if and only if Pol r contains one of the operations listed in Proposition 1. Other­ wiser is NP-complete.

3 Tractable amalgams

In this section we give a complete solution of Problems 1,2 for amalgams of relational clones. Throughout the section A,B are finite sets, D = An B, and RA , Rs are relational clones on A, B respectively. First, we reduce Problems 1,2 to the case when IDI = 1 and prove NP-completeness results in this case. Then we concentrate on tractable cases and present a solving algorithm for these cases.

3.1 The result

We assume that RA, Rs contain empty relations of any arity, because otherwise Pol (RA iXl Rs) contains a constant oper­ ation, and therefore RA iXl Rs is tractable by Proposition 1.

The case when D is empty was completely investigated in [Cohen et at., 2000a].

Proposition 2 ([Cohen et al., 2000a]) If D 0 then CSP(RA iXl Rs) is polynomial time reducible to CSP(RA), CSP(Rs ). Hence, RA iXl Rs is tractable if and only if both RA , Rs are tractable.

So, we assume D to be non-empty.

Proposition 3 ([Jeavons et al., 1997; Jeavons, 1998b]) Iff is a unary polymorphism of a constraint language r then the problem class CSP(f(f)) where f(r) = {!(e) I e E r}, f(e) = {(f(al) , ... , f(an)) I (a1, ... , an) E {!},is polyno­ mial time equivalent to CSP(f).

By fb we denote the restriction of a (unary) operation f onto a set C. The following statement is straightforward.

Proposition 4 (I) Iff is a unary polymorphism of RA iXl Rs then fiA' fiB are polymorphisms of RA, Rs, respectively.

(2) CSP(RA iXl Rs) is polynomial time equivalent to CSP(JIA(RA) iXl fi 8 (Rs)).

( 3) If the amalgam RA iXl Rs is tractable then there is a poly­ morphism f of RA iXl Rs such that lf(D)I = 1. Otherwise, RA iXl Rs is NP-complete.

Therefore, we may restrict ourselves to the case IDI = 1; let D = { c}. In this case we need more notation and termi­ nology.

Definition 5 The relational clone RA [ Rs] is said to be monolithic ifRA = (RA U {D}) [Rs = (Rs U {D})l con­ tains no unary relation E with c f. E.

Let R1 denote the relational clone generated by the set RA U {e U {c} I e E RA} where c = (c, .. . , c) 2 · Obviously, RA <;;; R1. The clone R~ is defined analogously.

2 We do not specify the length of the tuple c = (c, . .. , c) , be­ cause it is always clear from the context.

In the following definition we introduce an auxiliary re­ lational clone on the 2-element set Z = {A, B} that de­ scribes interaction of the components of the amalgam. For an (n-ary) relation{} E RA, let {f = {(ai, ... ,an,A) I (ai, ... ,an) E I?A}U{(c, ... ,c,B)}. Wealsodefinethecor­ responding predicate Fe (xi, ... , Xn, y) which is true if and only if (XI, ... , Xn, y) E {f. The variable y will be called distinguished.

Definition 6 The meta-clone IRA is defined to be the set of all relations on Z expressible through a pp-formula of the form 3xi, ... , XnZI, ... , Zk<l>(xi, ... , Xn, YI, ... , Ym, ZI, ... , Zk) where <I> is a conjunction of predicates Fe for I? E Rt and YI, ... , Ym , ZI, ... , Zk are the distinguished variables.

The meta-clone IRE is defined in a similar way.

Lemma 1 Meta-clones IRA, IRE are relational clones on Z.

We now in a position to state the main result of this paper.

Theorem 3 Let IDI = 1. Then

I. if RA is monolithic then RA ~ RB is tractable if and only if Rt is tractable;

2. if both RA, RB are not monolithic then RA ~ RB is tractable if and only if Rt Rt, and IRA U IRE are tractable.

It is not hard to see that R1 , Rt ~ (RA ~ RB). There­ fore, by Theorem 1, Rt is tractable whenever RA ~ R8 is tractable. The converse inclusion follows from Lemma 2. Then, it can be proved by straightforward calculation that CSP(IRA U IRE) is polynomial time reducible to CSP(RA ~ RB). Finally, in Sections 3.2,3.3, we show how to reduce CSP(RA ~ RB) to CSP(IRA UIRB ), CSP(R1), and CSP(Rt).

Lemma 2 If RA is monolithic then CSP(RA ~ R8 ) is poly­ nomial time reducible to CSP(Rt).

Proof: Let RA be monolithic. We set out the proof in several claims.

CLAIM 1. For any a E A - { c}, there is a unary polymor­ phism fa of RA such that fa(a) =c.

_Let 9I, ... , 9k be the list of all unary polymorphisms of RA, and E = {ai = 9I(a), ... ,ak = 9k(a)}. Sup­ pose that c (j. E. Since RA is monolithic, E (j. RA. Therefore, there is a polymorphism h(xi, . . . , xn) such that h(bi, ... , bn) (/. E for some bi E E, say, bi = aj,. The operation h' (x) = h(gj 1 (x), . .. , 9in (x)) is also a polymor­ phism ofRA [Poschel and Kaluznin, 1979], and h'(a) fj E, a contradiction.

CLAIM 2. RA is invariant under the constant operation c.

Since D = {(c)} E RA, for any a E A- {c}, we have fa(c) = c. This implies lfa 1 (A) I ~ IAI - 1 for any ai E A- {c}. Then choosing an element a2 E fa 1 (A) - {c} we get lfa 2 (ia 1 (A))I ~ IAI - 2. Continuing the process we eventually obtain an operation f ( x) = f a 1 ( ··· f a 1 ( x) ... ) such that If (A) I = 1. As f (c) = c, f is the required constant operation.

Claim 2 implies that if I? E RA is non-empty then c E I?· CLAIM 3. The operation g on AUB where g(x) = c if x E A and g(x) = x if x E B is a polymorphism of RA ~ RB.

Take{} E RA ~ RB and d E 1? = {}AU {}B, {}A E RA, {}B E RB. If d E {}B then g(d) = d E 1?· If d E {}A then {}A f:. 0, c E {}A~{}, and thereforeg(d) = c E g.

Finally, for any{} = {}AU I?B E RA ~ RB, g(g) = {}B or g(g) = I?B u {c}. This means that g(RA ~ RB) = Rt, and by Proposition 3, CSP(RA ~ RB) is polynomial time equivalent to CSP(Rt). 0

3.2 The Split Problem

We transform a problem over an amalgam so that the interac­ tion of its components becomes more transparent.

Lemma 3 If RA [ RB] is not monolithic then there is a rela­ tion O"A ERA [oB E RB] ofarity lA [lB] such thatc fj OA {C (/. OB}.

Proof: Let E E RA be such that c (j. E. Since E belongs to the clone generated by RA U { D}, it can be expressed by a pp-formula

<I>(x,yi, ... ,yn,ZI, ... ,zm) 1\ Po(zi) 1\ . .. I\ Po(zm) where <I> uses predicates from RA. As is easily seen, the relation P<T(x,zi, ... ,zm) = 3yi,···,Yn<I>(x,yi,···,Yn, ZI, ... , Zm) satisfies the required conditions. 0

Let P = (V; A U B; C) be a problem instance from CSP(RA ~ RB). Fix a representation {} = {}A U {}B, {}A E RA, {}B E RB for every constraint relation g. The split problem Pis defined to be the triple (V; AU B; C) (see Fig.1) in which

• V = VA U VB U V~ U VJJ where for every v E V there are vA E VA and v 8 E VB, and for every constraint C E C th I lA E V' d I IB V' . I ereareue, ... ,ue Aan we, ... ,we E 8 , etus d t - - h I lA I IB eno e ue, wet e sequences ue, ... , ue, we, ... , we respectively;
• C = CA U CB U C' where for every C = (s, e) E C, s = (VI, ... , vn), we include 3 constraints
• ((v~, ... , v~, ue), gA) E CA, {}A = (g x oA) u {c};
• ( ( vf, ... , vt;, we), g8) E C B, g8 = (g x o B) u {c};
• ((ue, we), o) E C' where o is the lA +lE-ary relation (oA X {c}) U ({c} X o8 ).

The following lemma is straightforward.

Lemma 4 P is equivalent to P.

On the one hand, the restrictions ofP on VA U V~, V8 U VJJ are problems from CSP(R1), CSP(Rt ) respectively. On the other hand, the implicit constraint relation arising on the set V~ in this problem can be treated as a relation on the 2element set { o A, D 1 A}, and correspond, in fact, to the rela­ tions from IRA. Therefore, the meta-clones describe the inter­ action of two parts of the split problem.

3.3 Solving the Split Problem

Let us assume that R1, Rt, IRA U IRE are tractable, and RA, RB are not monolithic. By Theorem 2, there is either (1) constant, or (2) semilattice, or (3) majority, or (4) affine oper­ ation f such that every relation from IRA U IRE is invariant un­ der f. We show that under this assumption the split problem P can be reduced to problems from CSP(R~), CSP(R~) in polynomial time.

We divide Pinto two subproblems f5 A = (VA UVA.; A; C A) and Ps = (Vs U VB; B; Cs) from CSP(R~), CSP(R~) re­ spectively. Recall also that C = { C1 , ... , Cq} . Then set

Let also mappings 'l/JA: a Au {c} ---+ Z, 'l/Js: as u {c} ---+ Z be defined as follows

ThenSA = 'l/JA(SA) = {('¢A(a~1 , ... ,a~1 ), ... ,'lj;A(a~.' .. . , a~.)) I (a~,, ... , a~.) E SA} is a q-ary relation - l from ~A. and Ss = 'l/Js(Ss) = {('lf;s(b~,, ... ,bJ,), ... ,'l/Js(b~., ... ,b~.)) I (b~,··.:_··b~.) E Ss} isaq-ary relation from ~s. A solution to P exists if and only if there are solutions <pA E SA, <ps E Ss such that '¢A<pA = 'l/Js<ps or, equivalently, if SA n S s f:. 0. The ith component of a tuple d will be denoted by d(i] . Fix tuples a E a A, bE as.

CASE 1. RA U Rs is invariant under a constant operation. Without loss of generality we may assume that the constant operation map~ Z to A. Then ei~er SA JS s] is em2!)', or (A, ... ,A) E SA [(A, ... ,A) E Ss]. If SA= 0 orSs = 0 then SA or Ss is empty, consequently, f5 has no solution. If SA, S s f:. 0 then f5 A has a solution <p A E SA such that <pA(u~) = a(i] for all C E C, 1 :::; i :::; lA, and Ps has a solution <ps E Ss with <ps(wb) = c for all C E C, 1:::; j:::; ls . As is easily seen, '¢A<pA = 'l/Js<ps.

We need some additional notation. Let f2 be an n-ary re­ lation, and I= {i1 , ... ,ik} ~ {1, ... ,n}; then 7ri(f2) de­ notes the k-ary relation { 1r I (d) I d E f2} where 1r I (d) = (d(il], ... , d(ik]). For a problem instance P = (W; D; C) and a constraint (s, f2), we denote the problem instance ( W; D; C U { ( s, t2)}) by P U { ( s, f2)} .

CASE 2. ~A U Rs is invariant under a semilattice opera­ tion f.

Without loss of generality we may assume that f(A, A) = f(A, B) = f(B, A) = A, f(B, B) = B. Then [Jeavons et al., 1997] any relation 0 f:. f2 E RA U Rs contains the tuple maxe where maxe(i] =A if A E 7r{i}(f2), and maxe(i] = B otherwise. We employ the following algorithm.

Until no new constraint added, for each C E C do

• Solve the problems P AU { (ue, a A)}, Ps U j (we, {c}) }.
• If one of them has no solution then replace P A with f5 Au {(ue, {c})} and Ps with Ps u {(we,as) }.
• Solve the problems PA U { (ue, {c}) }, Ps Uj (we, as)}.
• If one of them has no solution then replace P A with P Au { (ue, a A)} and Ps with Ps u {(we, {c})}.

Notice that this algorithm is quite analogous to establishing ]-consistency [Jeavons et al., 1998; Dechter and van Beek, 1997; Cooper, 1989]. Let PA, P's be the obtained problems, SA, S's defined for PA, P's in the same way as SA, S s, and s~ = '¢A(SA), s~ = 'l/Js(S's). Clearly, SAn Ss f:. 0 -1 -1 -1 if and only if SA n S s f:. 0. Moreover, since 7r{;}S A = -1 _, _, 7r{i}S S· for any i, we have maxs' = maxs' E SAnS s A B -1 -1 - whenever SA, S s f:. 0. Thus, P has a solution if and only if PA, P's have solutions.

CASE 3. ~A URs is invariant under a majority operation f. In this case any (n-ary) relation f2 E RA U ~s is 2decomposable [Jeavons et al., 1998], that is every n-tuple d such that, for any 1 :::; i,j :::; n, (d(i],d(j]) E 7r{i,j}f2, be­ longs to [!. Therefore, SA n S s f:. 0 if and only if there is a tuple d such that ( d(i], d(j]) E 1r { i,j} (SA) n 1r { i,j} (S s), for any 1 :::; i, j :::; q .

The latter condition is encoded by the constraint satis­ faction problem (W; Z; C") in which W = { z1 , . . . , zq}, and for any 1 :::; i, j :::; q, there is the constraint ((z;,zj),7r{i,j}(SA) n 7r{i,j}(Ss)). Since all the constraint relations are in ~A U Rs, this problem can be solved in poly­ nomial time (see [Jeavons et al., 1998]). We just have to find relations of the form 1r { i,j} (SA), 1r { i,j} (S s). To this end we consider the problems

and include a tuple (X, Y) in 7r{;,j}(SA) if and only if the problem f5~ 1 (X, Y) has a solution. The relation 7r{i,j}(Ss) can be found in the same way.

CASE 4. ~A U ~s is invariant under an affine operation f.

This case is, in fact, impossible. To show this, notice that the relation (} = (a A x A 1 A) U {c} belongs to R!. Then the relation

i~ expressible 1;_y the pp-for~ula Pr(x1 ,x2) = 3y1 ,y2 ,z Pe (Yl, Y2, z) 1\Pu A (Yl, X1) 1\ Pu A (y2, x2), and, therefore, be­ longs to IRA. However, f does not preserver.

ExampleS LetX = {0,1,2,3},Y = {O,I,2,3},D = {c}. Consider the relations on A = X U D, B = Y U D:

We are going to show that the amalgam {(}A} tXl { g s} is tractable. To this end we notice that (}A [g s] is invariant with respect to fA, hA Us, gs, hs] such that

• !A(x,y) = x if x = c, !A(x,y) = y if x E X; f S (X, Y) = X if X E Y, j S (X, y) = y if X = c;
• gs(x,y)=xifx=c,gs(x,y)=yifxEY;
• h A (X' y' z) = X- X y +X z if X' y' z E X, h A (X' y' z) = x otherwise;
• hs(x,y,z) = x-yy+yzifx,y,z E Y,hA(x,y,z) = x otherwise

where + x, +y denote addition modulo 4 in X, Y re­ spectively. We define the relational clones RA, Rs to be lnv({!A,hA}), lnv({fs,gs,hs}). Clearly, (}A E RA, (}s E Rs. We show that RA tXl Rs is tractable.

As is easily seen, the operations fA, hA preserve the rela­ tion X, and fs, gs, hs preserve Y. Therefore, X E RA C RA, Y E Rs ~ Rs, hence, RA, Rs are not monolithic. ii: is straightforward to show that every relation from IRA U JR8 is invariant with respect to the semilattice operation f where f(A, B)= j(B, A)= f(B, B)= B, f(A, A)= A.

By Schaefer's Theorem, IRA U IRs is tractable, therefore, to show the tractability of RA tXl Rs we have to show the tractability of R!, R~. For any (} E RA, the operations !A, hA preserve the relation(} U {c}, and, for any g E R8 , fs, gs, hs preserve(} U {c}. Hence, R! = RA, R~ = Rs.

We sketch a solving algorithm for CSP(RA) and leave to the reader verifying its soundness. Let P = (V; A; C) E CSP(RA).

• Set W = { v E V I for any (s, g) E C such that v E s, c E 1f{v}(g)}, and U = V- W.
• Every constraint relation of Plu = (U; X; Cl) where, for any (s, g) E C, there is (s n U, 1fsnu(g)) E Clu is invariant with respect to x - x y + x z. Find a solution 'lj!: U-+ X to Plu by making use of standard algorithms from number theory.
• Setcp(v) = 'lj!(v) ifv E U andcp(v) = cotherwise. The mapping cp: V -+ A is a solution to P.

The algorithm for CSP(Rs) is analogous.