Making Bound Consistency as Effective as Arc Consistency

1 Introduction

Constraint solvers work by interleaving branching with constraint propagation. Arc consistency (AC) and bound consistency (BC) are the most common kinds of constraint propagation that solvers enforce. BC is used on a constraint when AC is too expensive. This happens when domains are too large, or when AC is too hard to enforce on the constraint. For instance, given n variables and d values per domain, the alldiff constraint can be made BC in O(n · log(n)) time ([Puget, 1998]) whereas O(n1.5d) time is required for AC ([R´egin, 1994]). BC is polynomial on the Nvalue constraint whereas AC is NP-hard ([Bessiere et al., 2006]). The negative counterpart of BC is that BC generally prunes less values than AC.

Our main contribution is to characterize the unique maximal class of binary constraints on which AC and BC are equivalent however the initial domain is pruned. We give an easy test for membership of a constraint to that class.

Since BC is defined according to a total ordering of the domains, so is the case for the class of constraints on which BC is equivalent to AC. Our second contribution is to give a polynomial algorithm for reordering the domains so that a given constraint becomes a member of that class. Consider the constraint alldiff (x1, x2, x3), where x1, x2 ∈ {b, c}, x3 ∈ {a, b, c, d}. BC does not remove any value because every bound belongs to a satisfying tuple. By reordering the domain of x3 with b < c < a < d, BC removes b and c from x3 and becomes equivalent to AC. A (cheaper) BC propagation can be applied to the constraint instead of AC. As a third contribution, we extend our results to non-binary constraints.

∗Supported by the project CANAR (ANR-06-BLAN-0383-02).

Our results give the theoretical basis for several directions of research such as incrementally detecting during search constraints for which BC becomes equivalent to AC, or designing efficient specialized reordering algorithms for global constraints. In the short run, our algorithms can be used in a preprocessing phase to detect on which constraints to use the BC propagator instead of the AC propagator. This will particularly pay off when a CSP defines a generic problem, solved repeatedly with the same kernel of constraints plus a few additional ones (e.g., a time tabling problem solved every month with different requirements). The preprocessing cost will be amortized on the several runs.

2 Background

A constraint network N consists of a sequence of variables X = (x1, . . . , xn), a sequence of domains D = {D1, . . . ,Dn}, where the domain Di is the finite set of at most d values that variable xi can take, and a set C of e constraints that specify the allowed combinations of values for given subsets of variables. A relation R of arity k is any set of tuples of the form (a1, a2, . . . , ak), where all aj's are values from the given universe U. A constraint of arity k is a pair C = (X, R), where X is a sequence of k variables and R is a relation of arity k. We use notation DX for the Cartesian product of domains Πxi∈XDi, and R[DX ] for R ∩ DX , that is, the relation restricted to tuples over the Di's. The negation C¬ of C = (X, R) is the constraint (X, R¬), where R¬ = U X \ R is the complement of R.

An assignment t to a set of variables X is a function from X to the universe of values U. t[x] is the value of x in t. An assignment t to a sequence X = (x1, . . . , xk) of variables, or to a superset of X, satisfies C = (X,R) iff (t[x1], . . . , t[xk]) ∈ R. t[xi/b] is the assignment obtained from t when replacing t[xi] by b. A solution of N = (X,D, C) is an assignment t to X such that t[xi] ∈ Di for all xi ∈ X, and t satisfies all the constraints in C.

Orderings An ordered signature is a triple Σ = (X,D,<), where X = (x1, . . . , xk) is a sequence of variables, D = (D1, . . . ,Dk) is a sequence of domains for them, and < is a sequence (<1, . . . ,<k), where <i is a total order on Di. We consider that Σ is also an ordered signature for any Y ⊆ X. min<i Di (resp. max<i Di) is the minimum (resp. maximum) element in Di according to <i. Given a, b, c ∈ Di, med<i (a, b, c) is the median value of a, b, c according to <i. When the ordering is clear, we will write minDi, maxDi, med(a, b, c). We write [a..c] for the set of values b with a ≤ b ≤ c, S for [minS..maxS], and a - 1 (a + 1) for the immediate predecessor (successor) of value a. We write D′i < Di as a shorthand for ∀b ∈ Di, ∀b′ ∈ D′i , b′ < b and we write D′ ⊆ D for ∀i, D′i ⊆ Di. For instance, given a < b < c we have min(c, a) = a, med(a, c, b) = b, med(a, c, c) = c, [a..c] = {a, b, c}, c - 1 = b, {a, b} < {c}.

Consistencies Constraint solvers maintain a local consistency during search. The most usual ones are defined below.

Definition 1 (local consistencies) Let Σ = (X,D,<) be an ordered signature and C = (X, R) be a constraint. A support for bi ∈ Di is a tuple t ∈ R[DX ] such that t[xi] = bi. A bound support for bi ∈ Di is a tuple t ∈ R[Πxj∈XDj] such that t[xi] = bi. The domain Di is AC (resp. RC) on C if any bi ∈ Di has a support (resp. a bound support), and it is BC on C if minDi and maxDi have a bound support. The constraint C is BC (resp. RC, AC) if for all xi ∈ X, Di is BC (resp. RC, AC) on C.

Our BC is the most common version of bound consistency, called BC(Z) in [Bessiere, 2006]. Slightly abusing words, for a binary constraint ((x1, x2), R) we say that value a2 is a (bound) support for value a1, instead of the tuple (a1, a2).

Let (X,D, C) be a constraint network, (X,D,<) an ordered signature, and Φ a local consistency. Φ(D, C) is the closure of D for Φ on C, that is, the sequence of domains obtained from D once for every i we have removed every value bi ∈ Di that is not Φ-consistent on a constraint in C. AC(D, C) is also denoted by D∗ .

Two local consistencies may behave the same. Our definition of equivalence requires stability under domain reductions (due to instantiations and propagation of other constraints).

Definition 2 (equivalence of local consistencies) Given an ordered signature Σ = (X,D,<) and a constraint C, two local consistencies Φ1 and Φ2 are called equivalent on C for Σ if for any domain D′ ⊆ D, Φ1(D′ , C) = Φ2(D′ , C).

Classes of constraints Monotone constraints have been introduced by Montanari [Montanari, 1974] in the binary case. We give a definition for any arity.

Definition 3 (in/decreasing,monotone) Let Σ = (X,D,<) be an ordered signature and C = (X,R) a constraint. A variable xi ∈ X is said to be increasing (resp. decreasing) for Σ on C iff for any tuple t ∈ R and any value a ∈ Di such that a > t[xi] (resp. a < t[xi]), the tuple t[xi/a] is in R. A constraint in which every variable is decreasing or increasing is said to be monotone.

Definition 4 (row convex [van Beek and Dechter, 1995])

Let Σ = (X,D,<) be an ordered signature. A constraint C = (X,R) is row convex for Σ iff for every xi ∈ X and any instantiation t-i in DX\{xi} , the set of values in Di that extend t-i to a tuple in R[DX ] is an interval in Di.

Connected row convex constraints have been introduced in [Deville et al., 1999] only for binary constraints, but [Jeavons et al., 1998] defined med-closed constraints and showed that the constraints that are binary and med-closed are exactly the connected row convex constraints [Jeavons et al., 1998, example 4.7]. We thus give the most general definition.

Definition 5 (med-closed constraint) Let Σ = (X, D,<) be an ordered signature. C = (X, R) is med-closed for Σ if for any three tuples t, t′ , t′′ in R[DX ], the tuple tm defined by ∀x ∈ X, tm[x] = med<x (t[x], t′ [x], t′′ [x]) is in R.

Example 1 Let D1 = D2 = D3 = {0, 1, 2} with the natural order on each domain. C = ((x1, x2, x3), {000, 010, 101, 222}) is not med-closed because the median of 010, 101, 222 is the forbidden tuple 111. By reordering D2 such that 1 <2 0 <2 2, we obtain a med-closed constraint: for any three tuples the median tuple is 000 or 101, which satisfy C. ♣

3 Equivalent Consistencies in the Binary Case

Enforcing BC on a constraint generally prunes less values than enforcing AC. However, in some particular cases, BC and AC can be equivalent. This is the case, e.g., for the constraint x < y, whatever the domains of x and y.

In this section, we analyze the properties that make BC and RC equivalent on binary constraints. We do the same for RC and AC, and then we derive a necessary and sufficient condition for having BC equivalent to AC on a binary constraint.

Our characterization is for convex initial domains (of the formD), that is, it characterizes the cases when BC is equivalent to AC on every subdomain D′ ⊆ D. We will see in Section 5 why this is not a restriction. We also restrict our analysis to domains (D)∗ , that is, the subdomain of an initial (convex) domain D where all values have a support. This is a reasonable restriction because a single preprocessing phase of AC is enough. It discards dummy values that prevent from finding any nice characterization.

Lemma 1 Let X = (x1, x2), Σ = (X,D,<), and C = (X, R). BC and RC are equivalent on (X, (D)∗ ) for C iff C is connected row convex for Σ∗ = (X, (D)∗ , <).

Proof. (⇐) Assume C is connected row convex for Σ∗ and let D′ ⊆ (D)∗ . By definition, if D′ is RC, it is also BC for the same ordering. Conversely, assume D′ is BC for C. Let a = min1D′1 and c = max1D′1 . By definition of BC, a and c have bound supports ta and tc wrt D′ on C. Take any b ∈ D′1 . b has a support tb in (D)∗ because b ∈ D′1 ⊆ (D)∗1 . Let tm be the tuple med(ta, tb, tc). Since by construction ta, tb, and tc are in (D)∗ and satisfy C, and since C is connected row convex for Σ∗ , tm is a satisfying tuple for C. By definition of median, tm[x2] ∈ {ta[x2], tc[x2]} ⊆ D′2 . In addition, tm[x1] = b because a < b < c. Therefore, tm is a bound support for b in D′ , and b is RC. The same reasoning applies for values in D′2 . As a result, D′ is RC.

(⇒) Assume now that C is not connected row convex for Σ∗ . We show that there exists D′ ⊆ (D)∗ that is BC but not RC for C. Since C is not connected row convex, there exist a1a2, b1b2, c1c2 ∈ (D)∗ with a1a2, b1b2, c1c2 ∈ R but tm = med(a1a2, b1b2, c1c2) /∈ R. Without loss of generality, assume a1 ≤ b1 ≤ c1. We have tm ̸= b1b2 because b1b2 ∈ R. Hence, b2 ̸= tm[x2] = med(a2, b2, c2) because tm[x1] = b1. Assume b2 < a2 < c2 (the other cases are similar).

If b1 has no support in [a2..c2]∩(D)∗2 , consider the domain D′ = ([a1..c1] ∩ (D)∗1 , {a2, c2}). Then, a1, a2, c1, c2 have a bound support in D′ , and so D′ is BC, but b1 ∈ D′1 has no bound support in D′ . Conversely, if b1 has a support b1b′2 in [a2..c2] ∩ (D)∗2 , consider D′ = ({b1}, [b2..b′2 ] ∩ (D)∗2 ). By construction, b2 < a2 ≤ b′2 ≤ c2 and thus b1a2 = tm /∈ R. So, b1, b2, b′2 have a bound support in D′ , and so D′ is BC, but a2 has no bound support in D′ . ✷

Proof. (⇐) Suppose C¬ is row convex for Σ∗ and let D′ ⊆ (D)∗ . By definition, if D′ is AC, it is also RC. Conversely, assume D′ is RC for C. Let b1 ∈ D′1 and tb ∈ (D′ )∗ ⊆ (D)∗ be a bound support for b1 in D′ . We write ai = minD′i , bi = tb[xi], ci = maxD′i . We have tb ∈ R, so tb /∈ R¬. Hence, b1a2 /∈ R¬ or b1c2 /∈ R¬ because C¬ is row convex for Σ∗ and a2 ≤ b2 ≤ c2. Thus, at least one tuple among b1a2 and b1c2 is in R and b1 has a support in D′ . Therefore, D′ is AC.

(⇒) Assume now that C¬ is not row convex for Σ∗ . Without loss of generality, let b1 ∈ (D)∗1 , a2, b2, c2 ∈ (D)∗2 with a2 < b2 < c2 such that b1a2, b1c2 ∈ R¬ and b1b2 /∈ R¬. We thus have b1a2, b1c2 /∈ R and b1b2 ∈ R. Let a1, c1 ∈ (D)∗1 be supports of a2 and c2, respectively, and let D′ = ({a1, b1, c1}, {a2, c2}). Then b1 has a bound support but no support in D′ . Therefore, D′ is RC but not AC. ✷

From the results above, we derive the following characterization of binary constraints for which BC is equivalent to AC. Call Crow+row¬ for a binary constraint which is connected row convex and whose negation is row convex.

4 Membership to Crow+row¬

We give a characterization of Crow+row¬ constraints given a signature. It will be used to recognize such constraints. Intuitively, if we represent a Crow+row¬ constraint as a Boolean matrix, all 0 entries are located in two opposite corners, forming two "monotone regions" which do not share any line or column (see Example 2). The various regions in the matrix are captured by the following definition (monotonicity of the regions containing zeroes is captured by Proposition 1).

Definition 6 (Crow+row¬-partition) Let X = (x1, x2), Σ = (X,D,<), and C = (X,R). A Crow+row¬-partition of D for C and Σ is a partition of Di in (Di ,D= i ,D+ i ) (for i ∈ 1, 2) such that:

1. D= 1 = {a1 ∈ D1 | ∀a2 ∈ D2, a1a2 ∈ R} and D= 2 = {a2 ∈ D2 | ∀a1 ∈ D1, a1a2 ∈ R},
2. D1 <D= 1 <D+ 1 and D2 <D= 2 <D+ 2 ,
3. either (i) R[D+ 1 ×D2 ] =D+ 1 ×D2 andR[D1 ×D+ 2 ] = D1 ×D+ 2 , or (ii) R[D1 × D2 ] = D1 × D2 and R[D+ 1 ×D+ 2 ] =D+ 1 ×D+ 2 .

Observe that independently of Σ, such a partition, if any, is unique up to the order of values inside some part Dr i and the symmetry between < and >.

Example 2 Let Σ = ((x1, x2), (D1,D2), (<1,<2)) with D1 = {a1, . . . , d1}, D2 = {a2, . . . , f2}, a1 < · · · < d1 and a2 < · · · < f2. Let C = ((x1, x2),R) be a constraint, with R defined by the Boolean matrix below.

The following result captures the fact that Crow+row¬ constraints are exactly those with the form as in Example 2. Cases (i) and (ii) are symmetric to each other, depending on the corners where zeroes lie (upper left and lower right in Case (i), opposite in Case (ii)).

Proposition 1 Let X = (x1, x2), Σ = (X,D,<), and C = (X,R). C is Crow+row¬ on (X,D∗ ,<) iff there is a Crow+row¬-partition (Di ,D= i ,D+ i ), i = 1, 2 of D∗ such that one of the following holds

• (i) x1 (resp. x2) is increasing in the constraint (X, R[D1 × D2]) (resp. (X,R[D1 × D2 ])), and decreasing in (X, R[D+ 1 ×D2]) (resp. (X,R[D1 ×D+ 2 ])), or
• (ii) x1 (resp. x2) is decreasing in the constraint (X, R[D1 × D2]) (resp. (X,R[D1 × D2 ])), and increasing in (X, R[D+ 1 ×D2]) (resp. (X,R[D1×D+ 2 ])).

Proof. (Sketch.) The "if" direction is easy. For the "only if" direction, we know from [Cohen et al., 2000, Example 12] that, as a connected row convex constraint, C is equivalent to a conjunction C of constraints each of the form (ℓi) or (ℓ1 ∨ ℓ2), where ℓi is either xi ≥ ai or xi ≤ ai for some ai ∈ D∗ i . Moreover, since all values in D∗ have a support, there is no nontrivial unary constraint in C (since, e.g., the unary constraint x1 ≥ 2 eliminates any support for 1).

By symmetry, let C = (x1 ≥ a1 ∨x2 ≥ a2) be a constraint in C (case (i); case (ii) is symmetric with a clause (x1 ≥ a1 ∨ x2 ≤ a2)). We claim that any other constraint in C is of the form (x1 ≥ a′1 ∨ x2 ≥ a′2 ) or (x1 ≤ a′1 ∨ x2 ≤ a′2 ). Indeed, if there was a constraint, say, (x1 ≥ a′1 ∨x2 ≤ a′2 ) in C, then for any value b1 ∈ D∗ 1 , b1 < a1, a′1 , either b1 would have no support (case a2 > a′2 ), contradicting the definition of D∗ , or its non-supports would form a non-convex interval D∗ 2 \ [a2..a′2 ] of D∗ 2 , contradicting the row convexity of C¬.

So C contains only (≤, ≤) and (≥, ≥)-constraints. Now we claim that every two constraints (x1 ≥ a1 ∨ x2 ≥ a2), (x1 ≤ a′1 ∨x2 ≤ a′2 ) are such that a1-1 < a′1 +1 and a2-1 < a′2 + 1. Indeed, if a1 - 1 ≥ a′1 + 1, then either value a′1 + 1 ∈ D∗ 1

has no support (case a2 > a′2 ), or its non-supports form a non-convex interval of D∗ 2 , a contradiction in each case.

To sum up, we have that values ruled out by ≥-literals are all less than values ruled out by ≤-literals.

Let D+ 1 = {b1 ∈ D∗ 1 | ∃a1, a2, b1 > a1, (x1 ≤ a1 ∨ x2 ≤ a2) ∈ C}, that is, values for D∗ 1 ruled out by ≤-literals, and similarly for D1 ,D+ 2 ,D2 . Moreover, let D= 1 = {a1 ∈ D∗ 1 | ∀a2 ∈ D∗ 2 , a1a2 ∈ R}, and similarly for D= 2 . As we can see, these collect all the remaining values. By construction and by the second claim above, we have that (Di ,D= i ,D+ i ) is a partition of Di and Di < D= i < D+ i . Finally, by construction, only ≤-literals constrain values in D+ 1 , so x1 is decreasing in (X,R[D+ 1 ×D2]), and similarly for the other cases. Finally, by construction again all other restrictions of R are satisfied by all tuples. ✷

5 Binary Constraints Renamability

Membership to the Crow+row¬ class of constraints is defined according to an ordered signature. In this section, we are interested in Crow+row¬-renamability, that is, finding whether there exists an ordering on the domains of the variables of a constraint that makes the constraint Crow+row¬.

We first give an easy result about the corresponding problem for monotone constraints. Observe that monotone binary constraints are a special case of Crow+row¬ constraints.

Proposition 2 Let X = (x1, x2), C = (X, R), and a couple of domains D for X. One can compute an ordered signature Σ = (X, D, <) such that C is monotone for Σ, or assert that there is none, in time O(d3 ).

Proof. (Sketch.) Without loss of generality, we look for a signature according to which every variable is increasing. For each variable xi, we build a directed graph Gi as follows. Consider x1 (the case of x2 is analogous). The vertices of G1 are the values in D1, and there is an edge (b1, a1) if and only if there is (a1, a2) ∈ R such that (b1, a2) is not in R. Clearly, the topological orders on Gi's, if any, are exactly those for which C is increasing. Time complexity is straightforward. ✷

We give an efficient algorithm for reordering domains so that a constraint becomes Crow+row¬, using Proposition 1. We first try to find a Crow+row¬-partition of the domains. We use an undirected graph to do so. If the partition exists, we try to reorder Di and D+ i so as to satisfy the in/decreasingness constraints in the characterization of Proposition 1. By symmetry, we look for reorderings such that R[D1 ×D2 ] is increasing, and R[D+ 1 ×D+ 2 ] is decreasing, that is, letting zeroes in the upper left and lower right corners of the matrix.

Definition 7 (Crow+row¬-graph) Let X = (x1, x2), C = (X, R), and a couple D of domains for X. The Crow+row¬- graph of C on D, written G(C), is the undirected graph (V, E) with V = (D1 ×D2)\R and for all a1a2, b1b2 ∈ R¬, {a1a2, b1b2} ∈ E ⇐⇒ a1 = b1 or a2 = b2.

Intuitively, the Crow+row¬-graph is the graph of zeroes in the matrix representation, where two zeroes are connected if they are on the same line or column. So the following lemma is a direct consequence of Proposition 1 (with the intuition coming from the matrix representation).

Lemma 3 Let X = (x1, x2), Σ = (X,D,<), and C = (X,R). The following are equivalent:

1. there is a Crow+row¬-partition (D1 ,D= 1 ,D+ 1 , D2 ,D= 2 ,D+ 2 ) of D∗ such that R[D+ 1 × D2 ] = D+ 1 ×D2 , R[D1 ×D+ 2 ] = D1 ×D+ 2 , R[D1 ×D2 ] is increasing, and R[D+ 1 × D+ 2 ] is decreasing for Σ∗ = (X, D∗ , <),
2. the graph G(C) has exactly two connected components C-,C+ (possibly empty), so that D1 = {a1 | a1a2 ∈ C-} and similarly for D+ 1 ,D2 ,D+ 2 , R[D1 × D2 ] is increasing, and R[D+ 1 ×D+ 2 ] is decreasing for Σ∗ .

Before we state the results about computing renamings, we show that, though our characterization concerns only the convex hull of domains, we can search reorderings of only the values in the domain (ignoring values in U \ D). The proof is straightforward since row and connected row convexity are defined according to actual domains (not ranges).

Proposition 3 Let X = (x1, x2), C = (X,R), and domains D for X. There is an ordered signature ΣU = (X, (D)∗ , <U), where <U is over the universe of values U, such that C is Crow+row¬ for ΣU, iff there is such a signature Σ′U = (X, (D)∗ , <′U ) for which (Di)∗ is convex in U wrt <′U , i = 1, 2. Moreover, the ordering over U \ (Di)∗ does not matter.

Hence, in the remainder of the paper we assume that only the values in the initial domain D∗ are reordered, instead of all the values in (D)∗ . Equivalently, we assume U = D∗ .

Proposition 4 Let X = (x1, x2), C = (X, R), and a couple of domains D for X. One can compute an ordered signature Σ∗ = (X, D∗ , <) such that C is Crow+row¬ for Σ∗ or assert that there is none in time O(d3 ).

Proof. The algorithm builds the graph G(C) in time and space O(d3 ) because there are O(d2 ) vertices (one for each pair (a1, a2) of values) and each vertex (a1, a2) can be connected to at most 2d other vertices (those of the form (a1, b2) or (b1, a2)). Then it computes the connected components of G(C) in time linear in G(C), i.e., O(d3 ). If there are at least three components, then it stops on failure (Lemma 3).

Otherwise, it computes D+ i and Di for i = 1, 2 by projecting the components, in time O(d2 ). Finally, it looks for ordered signatures Σ- = (X, (D1 ,D2 ),<-) and Σ+ = (X, (D+ 1 ,D+ 2 ),<+) so that R[D1 × D2 ] is increasing for Σ- and R[D+ 1 ×D+ 2 ] is decreasing for Σ+, in time O(d3 ) using Proposition 2. If there are none, then again it stops on failure (Lemma 3). Otherwise, it computes an ordered signature compatible with both Σ- and Σ+, which can be done by stacking the ordered subdomains over each other, in time O(d). The overall time complexity is O(d3 ). ✷

6 Renamability of Sets of Binary Constraints

In general, renaming several constraints that have variables in common can be done by storing for each variable on each constraint a permutation function that links the original ordering with the ordering that makes that constraint Crow+row¬. However, in Section 7, when decomposing a non-binary constraint into binary ones, the variables inside the non-binary constraint must be reordered the same way for each binary constraint, making all of them Crow+row¬ simultaneously. Call a set of constraints C (on X,D) Crow+row¬-renamable if there exists Σ = (X,D,<) such that ∀C ∈ C, C is Crow+row¬ for Σ. We show that deciding Crow+row¬- renamability of a set of binary constraints is tractable. 1 Lemma 4 says that, up to symmetries, there is essentially one signature making a constraint Crow+row¬ (if any).

Lemma 4 Let X = (x1, x2), C = (X,R), and D a couple of domains for X. If C is Crow+row¬-renamable, then there are partitions {D1 i , . . . ,Dki i } of Di, i = 1, 2, such that the ordered signatures (X,D, (<1,<2)) for which C is Crow+row¬ are exactly those satisfying the partial order D1 i < i · · · <i Dki i or D1 i > i · · · > iDki i for each i = 1, 2.

Proof. The symmetry between < and > is obvious. The partitions are built by grouping together values substitutable to each other (i.e., equal rows or columns in the matrix representation). As is clear on the matrix representation, any other partial order violates the characterization of Proposition 1. ✷

The algorithm which we propose for renaming sets of constraints proceeds inductively using the algorithm for an isolated constraint. Given {C1, . . . ,Ce}, it looks for the partial orders wrt which C1 is Crow+row¬. If none it stops, and otherwise it looks for such orders for C2. Again, if none it stops, and otherwise it looks for orders compatible with both. If none it stops, and otherwise it goes on with C3, etc.

By Proposition 1, the first one is Crow+row¬ wrt exactly those orders < 1,< 2 such that {a1} < {b1, c1} or {a1} > {b1, c1}, and {a2, b2} < {c2} < {d2, e2} or {a2, b2} > {c2} > {d2, e2}. Now the second one is Crow+row¬ iff {a3} < {b3} < {c3} or {a3} > {b3} > {c3}, and {a2} < {b2, c2} < {d2, e2} or {a2} > {b2, c2} > {d2, e2}. Thus the set of both constraints is Crow+row¬ wrt ρ1, ρ2, ρ3 iff {a1}ρ1 {b1, c1}, {a3}ρ3 {b3}ρ3 {c3}, and {a2}ρ2 {b2}ρ2 {c2}ρ2 {d2, e2}, ρ1, ρ2, ρ3 ∈ {<,>}. ♣

Proposition 5 Deciding whether a set of binary constraints N is Crow+row¬-renamable can be done in time O(ed3 ).

Proof. We show by induction that the algorithm sketched above is correct. The base case with no constraints is obvious, with the empty order for all xi. Now assume that (X,D, {C1, . . . ,Ck}) is Crow+row¬ wrt exactly the orders

1 This is somehow unexpected as connected row convex renamability of sets of binary constraints is NP-hard [Green and Cohen, 2008].

<i such that D1 i < D2 i < · · · < Dki i or D1 i > D2 i > · · · > Dki i . Assume w.l.o.g., using Lemma 4, that Ck+1 = ((xp, xq), R) is Crow+row¬ iff E1 i <′i E2 i <′i · · · <′i Eki i or E1 i >′i E2 i >′i · · · >′i Eki i , i = p, q. If there are orders extending both <i's and <′i 's, then clearly {C1, . . . , Ck, Ck+1} is Crow+row¬ for them. Otherwise, by construction there is no order making both {C1, . . . , Ck} and Ck+1 Crow+row¬.

Now to the time complexity. Renaming each constraint requires O(d3 ) (see Proposition 4). For each variable in the new constraint, two partial orders must be extended into a common one, which can be done by merging them in time O(d). Now there are e inductive steps, which concludes. ✷

7 Non-binary Crow+row¬ Constraints

So far we have considered only binary constraints. Recall that med-closed constraints give a generalization of connected row convex constraints to an arbitrary arity. Though we lose equivalence, Theorem 2 gives an interesting parallel to Theorem 1. The proof is a straightforward generalization of the (⇐) direction in Lemmas 1 and 2.

Theorem 2 (BC vs AC, n-ary) Let Σ = (X,D,<) and C = (X,R). If C is med-closed and C¬ is row convex for Σ∗ = (X, (D)∗ ,<), then BC and AC are equivalent on (X, (D)∗ ) for C.

The reverse does not hold, as can be seen with the ternary relation R = {1, 2, 3}3 \{332, 333}, which is not med-closed but for which BC and AC are equivalent.

Call med+row¬ for a med-closed constraint with row convex complement. Proposition 6 shows that such a constraint can be recognized via its projections over pairs of variables, that are all Crow+row¬. Proposition 7 shows the existence of a polynomial algorithm for med+row¬-renamability for constraints given in extension. The question remains open for constraints defined by an arbitrary predicate.

A constraint is binary decomposable if it is equivalent to the conjunction of its projections onto all pairs of variables.

Proposition 6 If C is (n-ary) med+row¬ wrt some ordered signature Σ, then it is binary decomposable, and each projection is Crow+row¬ (wrt Σ).

Proof. Because C is med-closed wrt Σ, it is binary decomposable [Gil et al., 2008]. By definition of med-closure, each projection is med-closed / connected row convex wrt Σ.

Now assume towards a contradiction that the projection ((xi, xj),Ri,j) of C has a non row convex complement. There is a value ai for xi and three values aj < bj < cj for xj (< is according to Σ) such that aiaj, aicj /∈ Ri,j (∈ R¬ i,j ) but aibj ∈ Ri,j . By definition of projection there is a support for aibj in R, that is, a tuple tait′ bjt′′ ∈ R, but no support for aiaj, aicj. So, tait′ajt′′ , tait′ cjt′′ /∈ R. Thus the instantiation tait′ t′′ of all variables but xj has a non convex support in R¬. This violates the assumption that R¬ is row convex. ✷

Note that the binary decomposition of R may be Crow+row¬ and R be non med+row¬. This is the case, for instance, for the join of the two constraints in Example 3 with the tuple b1b2b3 removed.

Proposition 7 Given an n-ary constraint C = (X, R) given in extension and a sequence of domains D for X, one can decide in polynomial time whether C is med+row¬-renamable.

Proof. First project R onto every pair of variables, yielding a set of binary constraints C, and decide whether (X,D, C) is Crow+row¬-renamable with Proposition 5. If it is not, then by Proposition 6 R is not med+row¬-renamable.

Otherwise, by the construction in Section 6, for all i we get a partial order <pi on the domain of xi, so that total orders according to which C is Crow+row¬ are exactly those extending <pi or >pi for all i. Given a set of (arbitrary) such total orders <= (<1, . . . , <n), one for each xi, we claim that R is med+row¬-renamable iff it is med+row¬ for <.

The "if" direction is obvious, so assume that R is med+row¬-renamable wrt some collection of total orders <′ . By Proposition 6 it is binary decomposable, so logically equivalent to C. Especially, any two values substitutable to each other in C are so in R as well. So R is med+row¬ wrt any order obtained from <′ by permuting two values substitutable to each other in C (as in the proof of Lemma 4). Moreover, by symmetry of med-closure and row convexity, it is also med+row¬ wrt any order obtained from <′ by reversing the order over any domain. Since by Proposition 6 and the construction, both < and <′ extend the partial order <pi or >pi for each i, < can be obtained from <′ by permuting substitutable values and reversing orders, so by symmetry again R is also med+row¬ wrt <, which ends to show the claim.

To conclude, one can decide whether R is med+row¬- renamable by considering only one (arbitrary) total extension of the <i's. Since R is given in extension, this can be done in polynomial time by testing the definitions of med-closure and row-convexity directly on the tuples in R. ✷

8 RelatedWork

Several classes of constraints have been identified for which the CSP is tractable, e.g., monotone constraints [Montanari, 1974; Woeginger, 2002] and row convex constraints [van Beek and Dechter, 1995; Deville et al., 1999]. Domain reordering techniques have been proposed to make a constraint member of the class [van Beek and Dechter, 1995; Green and Cohen, 2008]. However, it is seldom the case that a CSP only contains constraints of one class or allows a reordering leading all constraints to this class. Therefore, those theoretical results are not used in constraint solvers.

BC and AC have been proved to be equivalent on linear inequalities [Zhang and Yap, 2000] or on some arithmetic constraints, given some conditions on the type of domain reductions [Schulte and Stuckey, 2005]. In comparison, our work gives an exact characterization of the unique maximal class of binary constraints on which AC and BC are equivalent whatever the domain reductions that will appear during search. We insist on the importance of stability of equivalence under domain reductions. It allows a solver to use a BC propagator on that constraint without any risk to hinder AC propagation deeper in the search tree when domains have been modified.

9 Summary and Perspectives

We have characterized the constraints for which bound consistency prunes as many values as arc consistency, and we have proposed efficient algorithms for recognizing such constraints or sets of constraints, possibly by reordering the domains. Since bound consistency is usually cheaper to enforce than arc consistency, recognizing such constraints can save some pruning effort during search. The tractability of renaming non-binary constraints in intension being unknown, a promising direction for future research is to design efficient specialized algorithms for renaming global constraints so that a cheap BC propagator can be applied for enforcing AC. This can be seen as a new algorithmic perspective for designing efficient AC propagators.