Abstract Characterising tractable fragments of the constraint satisfaction problem (CSP) is an important challenge in theoretical computer science and artificial intelligence. Forbidding patterns (generic subinstances) provides a means of defining CSP fragments which are neither exclusively language-based nor exclusively structure-based. It is known that the class of binary CSP instances in which the broken-triangle pattern (BTP) does not occur, a class which includes all tree-structured instances, are decided by arc consistency (AC), a ubiquitous reduction operation in constraint solvers. We provide a characterisation of simple partially-ordered forbidden patterns which have this AC-solvability property. It turns out that BTP is just one of five such AC-solvable patterns. The four other patterns allow us to exhibit new tractable classes. Introduction The constraint satisfaction problem (CSP) provides a common framework for many theoretical problems in computer science as well as for many real-life applications. A CSP instance consists of a number of variables, a domain, and constraints imposed on the variables with the goal to determine whether the instance is satisfiable, that is, whether there is an assignment of domain values to all the variables in such a way that all the constraints are satisfied. Introduction The general CSP is NP-complete and thus a major research direction is to identify restrictions on the CSP that render the problem tractable, that is, solvable in polynomial time. Introduction A substantial body of work exists from the past two decades on applications of universal algebra in the computational complexity of and the applicability of algorithmic paradigms to CSPs. Moreover, a number of celebrated results have been obtained through this method; see (Barto 2014 ) for a recent survey. However, the algebraic approach to CSPs is only applicable to language-based CSPs, that is, classes of CSPs defined by the set of allowed constraint relations but with arbitrary interactions of the constraint scopes. For instance, the well-known 2-SAT problem is a class of languagebased CSPs on the Boolean domain {0, 1} with all constraint relations being binary, that is, of arity at most two. Introduction On the other side of the spectrum are structure-based CSPs, that is, classes of CSPs defined by the allowed interactions of the constraint scopes but with arbitrary constraint relations. Here the methods that have been successfully used to establish complete complexity classifications come from graph theory (Grohe 2007; Marx 2013) . Introduction The complexity of CSPs that are neither language-based nor structure-based, and thus are often called hybrid CSPs, is much less understood; see (Carbonnel and Cooper 2016) for a recent survey. One approach to hybrid CSPs that has been rather successful studies the classes of CSPs defined by forbidden patterns; that is, by forbidding certain generic subinstances. The focus of this paper is on such CSPs. We remark that we deal with binary CSPs but, unlike in most papers on (the algebraic approach to) language-based CSPs, the domain is not fixed and is part of the input. Introduction An example of a pattern is given in Figure 1(a) . This is the so-called broken triangle pattern (BTP) (Cooper et al. 2010b ) (a formal definition is given in Section 2). BTP is an example of a tractable pattern, which means that any binary CSP instance in which BTP does not occur is solvable in polynomial time. The class of CSP instances defined by forbidding BTP includes, for instance, all tree-structured binary CSPs (Cooper et al. 2010b ). There are several generalisations of BTP, for instance, to quantified CSPs (Gao et al. 2011) , to existential patterns (Cohen et al. 2015a) , to patterns on more variables (Cooper et al. 2014) , and other classes (Naanaa 2013; . Introduction The framework of forbidden patterns is general enough to capture language-based CSPs in terms of their polymorphisms. For instance, the pattern in Figure 1(b) captures the notion of binary relations that are max-closed (Jeavons and Cooper 1995) . Introduction Surprisingly, there are essentially only two classes of algorithms (and their combinations) known for establishing tractability of CSPs. These are, firstly, a generalisation of Gaussian elimination (Bulatov and Dalmau 2006; Dalmau 2006) , whose applicability for language-based CSPs is known (Idziak et al. 2010) , and, secondly, problems solvable by local consistency methods, which originated in artificial intelligence; see references in (Rossi et al. 2006) . The latter can be defined in many equivalent ways including pebble games, Datalog, treewidth, and proof complexity (Feder and Vardi 1998) . Intuitively, a class of CSP instances is solvable by k-consistency if unsatisfiable instances can always be refuted while only keeping partial solutions of size k "in memory". For instance, the 2-SAT problem is solvable by local consistency methods. Introduction For structure-based CSPs, the power of consistency methods is well understood: a class of structures can be solved by k-consistency if and only if the treewidth (modulo homomorphic equivalence) is at most k (Atserias et al. 2007) . Consequently, consistency methods solve all tractable cases of structurally-restricted bounded-arity CSPs (Grohe 2007) . For language-restricted CSPs, the power of consistency methods has only recently been characterised (Barto and Kozik 2014; Bulatov 2009 ). Contributions Our ultimate goal is to understand the power of local consistency methods for hybrid CSPs. On this quest, we focus in this article on the power of the first level of local consistency, known as arc consistency (AC), for classes of binary hybrid CSPs defined by forbidden (partially-ordered) patterns. Contributions The class of CSPs defined by forbidding BTP from Figure 1 (a) is in fact solvable by AC. But as it turns out, BTP is not the only pattern with this property. Contributions As our main contribution, we give, in Theorem 12, a complete characterisation of so-called simple partially-ordered forbidden patterns which have this AC-solvability property. Here the partial orders are on variables and domain values. It turns out that BTP is just one of five such AC-solvable patterns. The four other patterns allow us to exhibit new tractable classes, one of which in particular we expect to lead to new applications since it defines a strict generalisation of binary max-closed constraints which have already found applications in computer vision (Cooper 1999) and temporal reasoning (Dechter et al. 1991) . We also provide results on the associated meta problem of deciding whether a CSP instance falls into one of these new tractable classes. Contributions Given that AC is the first level of local consistency methods 1 and is implemented in all constraint solvers, an understanding of the power of AC is paramount. We note that focusing on classes of CSPs defined by forbidden patterns is very natural as AC cannot introduce forbidden patterns. While simple patterns do not cover all partially-ordered patterns it is a natural, interesting, and broad enough concept that covers BTP and four other novel and nontrivial tractable classes. We expect our results and techniques to be used in future work on the power of AC. Related work Computational complexity classifications have been obtained for binary CSPs defined by forbidden negative patterns (i.e., only pairwise incompatible assignments are specified) (Cohen et al. 2012) and for binary CSPs defined by patterns on 2 constraints (Cooper and Escamocher 2015) . Moreover, (generalisations of) forbidden patterns have been studied in the context of variable and domain value elimination rules (Cohen et al. 2015a ). Finally, the idea of forbidding patterns as topological minors has recently been investigated (Cohen et al. 2015b) . Takhanov 2015) recently considered the possible extensions of the algebraic approach from the language to the hybrid setting. Related work The power of the valued version of AC (Cooper et al. 2010a ) has been characterised (Kolmogorov et al. 2015b) . Moreover, the valued version of AC is known to solve all tractable finite-valued language-based CSPs (Thapper andŽivný) . Related work The omitted (parts of the) proofs are given in the full version of this paper (Cooper andŽivný 2016). Preliminaries CSPs and patterns A pattern can be seen as a generalisation of the concept of a binary CSP instance that leaves the consistency of some assignments to pairs of variables undefined. CSPs and patterns Definition 1 A pattern is a four-tuple X, D, A, cpt where: CSPs and patterns • X is a finite set of variables; • D is a finite set of values; • A ⊆ X × D is the set of possible variable-value assignments called points; the domain of x ∈ X is its non-empty set D(x) of possible values: D(x) = {a ∈ D | x, a ∈ A}; • cpt is a partial compatibility function from the set of unordered pairs of points {{ x, a , y, b } | x = y} to {TRUE, FALSE}. If cpt( x, a , y, b ) = TRUE (resp., FALSE) we say that x, a and y, b are compatible (resp., incompatible). For simplicity, we write cpt(p, q) for cpt({p, q}). CSPs and patterns We will use a simple figurative drawing for patterns. Each variable will be drawn as an oval containing dots for each of its possible points. Pairs in the domain of the function cpt will be represented by lines between points: solid lines (called positive) for compatibility and dashed lines (called negative) for incompatibility. CSPs and patterns Example 1 The pattern in Figure 9 is called LX. It consists of three variables, five points, six positive edges, and two negative edges. CSPs and patterns We refine patterns to give a definition of a CSP instance. CSPs and patterns where, for all x = y ∈ Y we have s(x), s(y) ∈ Rx,y. • A solution to P is a partial solution on X. CSPs and patterns For notational simplicity we have assumed that there is exactly one binary constraint between each pair of variables. In particular, this means that the absence of a constraint between variables x, y is modelled by a complete relation Rx,y = D(x) × D(y) allowing every possible pair of assignments to x and y. We say that there is a non-trivial constraint on variables x, y if Rx,y = D(v) × D(y). We also use the simpler notation Rij for Rx i ,x j . CSPs and patterns The main focus of this paper is on ordered patterns, which additionally allow for variable and value orders. CSPs and patterns Definition 3 An ordered pattern is a six-tuple X, D, A, cpt, <X , <D where: CSPs and patterns • X, D, A, cpt is a pattern; • <X is a (possibly partial) strict order on X; and • <D is a (possibly partial) strict order on D. CSPs and patterns A pattern X, D, A, cpt can be seen as an ordered pattern with empty variable and value orders, i.e. X, D, A, cpt, ∅, ∅ . CSPs and patterns Throughout the paper when we say "pattern" we implicitly mean "ordered pattern" and use the word "unordered" to emphasize, if needed, that the pattern in question is not ordered. CSPs and patterns We do not consider patterns with structure (such as equality or order) between elements in the domains of distinct variables. CSPs and patterns Definition 4 A pattern P = X, D, A, cpt, <X , <D is called basic if (1) D(x) and D(y) do not intersect for distinct x, y ∈ X, and (2) <D only contains pairs of elements a, b from the domain of the same variable, i.e., a, b ∈ D(x) for some x ∈ X. CSPs and patterns Example 2 The pattern in Figure 1 (a) is known as the broken triangle pattern (BTP) (Cooper et al. 2010b) . BTP consists of three variables, four points, three positive edges, two negative edges, <X = {x < z, y < z}, and <D= ∅. Given a basic pattern, we can refer to a point x, a in the pattern as simply a when the variable is clear from the context or a figure. For instance, the point z, γ in Figure 1 (a) can be referred to as γ. CSPs and patterns Example 3 The pattern in Figure 1 (b) is the (binary) max-closed pattern (MC). The pattern MC consists of two variables, four points, two positive edges, one negative edge, <X = ∅, and <D= {β < α, δ < γ}. MC (Figure 1(b) ) together with the extra structure α > γ is an example of a pattern that is not basic. CSPs and patterns For some of the proofs we will require patterns with additional structure, namely, the ability to enforce certain points to be distinct. CSPs and patterns Definition 5 A pattern with a disequality structure is a seven-tuple X, D, A, cpt, <X , <D, =D where: CSPs and patterns • X, D, A, cpt, <X , <D is a pattern; and • =D⊆ D ×D is a set of pairs of domain values that are distinct. CSPs and patterns An example of such a pattern is given in Figure 12 (b). Pattern occurrence Some points in a pattern are indistinguishable with respect to the rest of the pattern. Pattern occurrence Definition 7 A pattern is called unmergeable if it does not contain any mergeable points. Pattern occurrence Example 4 The points γ and δ in BTP (Figure 1 (a)) are not mergeable since they have different compatibility with, for instance, the point in variable x. The pattern LX (Figure 9 ) is unmergeable. Pattern occurrence Some points in a pattern (known as dangling points) are redundant in arc-consistent CSP instances and hence can be removed. Pattern occurrence Definition 8 Let P = X, D, A, cpt, <X , <D be a pattern. A point p ∈ A is called dangling if it is not ordered by <D and if there is at most one point q ∈ A for which cpt(p, q) is defined, and furthermore (if defined) cpt(p, q) = TRUE. Pattern occurrence Example 5 The point β in the pattern MC (Figure 1(b) ) is not dangling since it is ordered. Pattern occurrence In order to use (the absence of) patterns for AC-solvability we need to define what we mean when we say that a pattern occurs in a CSP instance. We define the slightly more general notion of occurrence of a pattern in another pattern, thus extending the definitions for unordered patterns (Cooper and Escamocher 2015) . Recall that a CSP instance corresponds to the special case of a pattern whose compatibility function is total. We first make the observation that dangling points in a pattern provide no useful information since we assume that all CSP instances are arc consistent, which explains why dangling points can be eliminated from patterns. Pattern occurrence Definition 9 A pattern is simple if it is (i) basic, (ii) has no mergeable points, and (iii) has no dangling points. Pattern occurrence From a given pattern it is possible to create an infinite number of equivalent patterns by adding dangling points or by duplicating points. By restricting our attention to simple patterns we avoid having to consider such patterns. Pattern occurrence Definition 10 Let P = X , D , A , cpt , < X , < D and P = X, D, A, cpt, <X , <D be two patterns. A homomorphism from P to P is a mapping f : A → A which satisfies: Pattern occurrence A consistent linear extension of a pattern P = X, D, A, cpt, <X , <D is a pattern P t obtained from P by first identifying any number of pairs of points p, q which are both mergeable and incomparable (according to <D) and then extending the orders on the variables and the domain values to total orders. Pattern occurrence Definition 11 A pattern P = X , D , A , cpt , < X , < D occurs in a pattern P = X, D, A, cpt, <X , <D if for all consistent linear extensions P t of P , there is a homomorphism from P to P t . We use the notation CSP SP (P ) to represent the set of binary CSP instances in which the pattern P does not occur. Pattern occurrence This definition extends in a natural way to patterns with a disequality structure. Pattern occurrence Remark 1 We can add a = b to a pattern, without changing its semantics, when a > b or a and b are unmergeable. Furthermore, all domain values a, b in an instance are distinct so there is an implicit a = b. Pattern occurrence Example 6 The pattern MC (Figure 1 For a pattern P , we denote by unordered(P ) the underlying unordered pattern, that is, unordered( X, D, A, cpt, <X , <D ) = X, D, A, cpt . Pattern occurrence For instance, the pattern unordered(BTP) is the pattern from Figure 1(a) without the structure x, y < z. Pattern occurrence The following three simple lemmas follow from the definitions. Pattern occurrence Lemma 1 If P occurs in Q and Q occurs in R, then P occurs in R. Pattern occurrence Lemma 2 If P occurs in Q and P does not occur in I, then Q does not occur in I, i.e. CSP SP (P ) ⊆ CSP SP (Q). Pattern occurrence Lemma 3 For any pattern P , unordered(P ) occurs in P . AC solvability Arc consistency (AC) is a fundamental concept for CSPs. AC solvability Points that are not arc-consistent cannot be part of a solution so can safely be removed. There are optimal O(cd 2 ) algorithms for establishing arc consistency which repeatedly remove such points (Bessière et al. 2005) , where c is the number of nontrivial constraints and d the maximum domain size. Algorithms establishing arc consistency are implemented in all constraint solvers. AC solvability AC is a decision procedure for a CSP instance if, after establishing arc consistency, non-empty domains for all variables guarantee the existence of a solution. (Note that a solution can then be found without backtrack by maintaining AC during search). AC is a decision procedure for a class of CSP instances if AC is a decision procedure for every instance from the class. Definition 13 A pattern P is called AC-solvable if AC is a decision procedure for CSP SP (P ). AC solvability The following lemma is a straightforward consequence of the definitions. AC solvability Lemma 4 A pattern P is not AC-solvable if and only if there is an instance I ∈ CSP SP (P ) that is arc consistent and has no solution. AC solvability The following lemma follows directly from Lemmas 2 and 4. AC solvability Lemma 5 If P occurs in Q and P is not AC-solvable, then Q is not AC-solvable. AC solvability As our main result we will, in Theorem 12, characterise all simple patterns that are AC-solvable. Pattern symmetry and equivalence For an ordered pattern P , we denote by invDom(P ), invVar(P ) the patterns obtained from P by inversing the domain order or the variable order, respectively. Pattern symmetry and equivalence Lemma 6 If P is not AC-solvable, then neither is invDom(P ), invVar (P ) or invDom(invVar(P )). Pattern symmetry and equivalence Proof: The claims follow from inversing the respective orders in the instance I of Lemma 4 proving that P is not AC-solvable. Pattern symmetry and equivalence Some patterns define the same classes of CSP instances. Lemma 7 If P occurs in P and P occurs in P , then P, P are equivalent. Pattern symmetry and equivalence Example 7 Let LX < be the pattern obtained from LX (Figure 9 ) by adding the partial variable order y < z. Due to the symmetry of LX, observe that LX and LX < are equivalent. Example 8 The two patterns shown in Figure 2 are also equivalent: (a) BTP do with structure x, y < z and c < d, and (b) BTP vo with variable order x < y < z. We will call these the variableordered and domain-ordered versions of BTP, respectively, when it is necessary to make the distinction between the two. BTP (Figure 1(a) ) will refer to the same pattern with the only structure x, y < z which again, by symmetry, is equivalent to both BTP do and BTP vo . New tractable classes solved by arc consistency Our search for a characterisation of all simple patterns decided by arc consistency surprisingly uncovered four new tractable patterns, which we describe in this section. The first pattern we study is shown in Figure 3 . It is a proper generalisation of the MC pattern (Figure 1(b) ) since it has an extra variable and three extra edges. New tractable classes solved by arc consistency Theorem 1 AC is a decision procedure for CSP SP (EM C) where EMC is the pattern shown in Figure 3 . New tractable classes solved by arc consistency Proof: Since establishing arc consistency only eliminates domain elements, and hence cannot introduce the pattern, it suffices to show that every arc-consistent instance I = X, D, A, cpt ∈ CSP SP (EM C) has a solution. We give a constructive proof. Let Figure 4 . To avoid the pattern EMC, we must have b h > am h . x1 < . . . < xn be an ordering of X such that EMC does not occur in I. Define an assignment a1, . . . , an to x1, . . . , xn recursively as follows: a1 = max(D(x1)) and, for i > 1, New tractable classes solved by arc consistency (1) For i > 1, we denote by pred(i) a value of j < i such that ai = a j i . Arc consistency guarantees that a j i exists and hence that ai and pred(i) are well defined. We claim that a1, . . . , an is a solution. Suppose, for a contradiction, that (aj, a k ) / ∈ R jk for some 1 ≤ j < k ≤ n. If there is more than one such pair (j, k), then choose k to be minimal and then for this value of k choose j to be minimal. New tractable classes solved by arc consistency We prove our claim that a1, . . . , an is a solution to I by induction on n. The claim trivially holds for n = 1 since a1 ∈ D(x1). It remains to show that if the claim holds for instances of size less than n then it holds for instances of size n. New tractable classes solved by arc consistency Let m0 = k and mr = pred(mr−1) for r ≥ 1 if mr−1 > 1. Let t be such that mt = 1. By definition of pred, we have 1 = mt < mt−1 < . . . < m1 < m0 = k which implies that this series is finite and hence that t is welldefined. New tractable classes solved by arc consistency We distinguish two cases: (1) j > m1, and (2) j < m1. Since (aj, a k ) / ∈ R jk and (am 1 , a k ) ∈ R jk we know that j = m1. New tractable classes solved by arc consistency Case (1) j > m1: Define b0 = a j k . By definition of a k , we know that a k ≤ a j k . Since (aj, a k ) / ∈ R jk and (aj, a j k ) ∈ R jk , we have b0 = a j k > a k . By our choice of j to be minimal, and since j > m1 we know that (am r , a k ) ∈ R mr k for r = 1, . . . , t. Indeed, by minimality of k, we already had (am r , am s ) ∈ Rm r ms for 1 ≤ s ≤ r ≤ t. Thus, since k = m0, we have (am r , am s ) ∈ Rm r ms for 0 ≤ s ≤ r ≤ t. New tractable classes solved by arc consistency ( New tractable classes solved by arc consistency By arc consistency, ∃b1 ∈ D(xm 1 ) such that (b1, b0) ∈ R m 1 k . We have (am 1 , aj) ∈ Rm 1 j by minimality of k and since m1, j < k. Since m1 = pred(k) and hence a k = a m 1 k , we have (am 1 , a k ) ∈ R m 1 k and (am 1 , b0) / ∈ R m 1 k by the maximality of a m 1 k in Equation (1). We thus have the situation illustrated in Figure 4 for h = 1. Since the pattern EMC does not occur in I, we must have b1 > am 1 . New tractable classes solved by arc consistency For 1 ≤ r ≤ t, let Hr be the following hypothesis. New tractable classes solved by arc consistency Hr: ∃s(r) ∈ {0, . . . , r − 1}, ∃p(r) < k, ∃br ∈ D(xm r ), with br > am r , such that we have the situation shown in Figure 5 . New tractable classes solved by arc consistency We have just shown that H1 holds (with s(1) = 0 and p(1) = j). We now show, for 1 ≤ r < t, that (H1 ∧ . . . ∧ Hr) ⇒ Hr+1. New tractable classes solved by arc consistency We know that (am r+1 , am r ) ∈ Rm r+1 mr and (am r+1 , br) / ∈ Rm r+1 mr , since mr+1 = pred(mr) and by maximality of am r = a m r+1 mr in Equation (1). Let q ∈ {0, . . . , r} be minimal such that Figure 6 . To avoid the pattern EMC, we must have br+1 > am r+1 . New tractable classes solved by arc consistency (am r+1 , bq) / ∈ Rm r+1 mq . We distinguish two cases: (a) q = 0, and (b) q > 0. New tractable classes solved by arc consistency If q = 0, then we have (am r+1 , a k ) ∈ R m r+1 k (from Equation (2), since k = m0), (am r+1 , b0) / ∈ R m r+1 k (since q = 0), (am r+1 , aj) ∈ Rm r+1 j (by minimality of k, since mr+1, j < k). By arc consistency, ∃br+1 ∈ D(xm r+1 ) such that (br+1, b0) ∈ R m r+1 k . We then have the situation illustrated in Figure 4 for h = r + 1. As above, from the absence of pattern EMC, we can deduce that br+1 > am r+1 . We thus have Hr+1 (with s(r+1) = 0 and p(r + 1) = j). New tractable classes solved by arc consistency If q > 0, then H1 ∧ . . . ∧ Hr implies that Hq holds. By minimality of q, we know that (am r+1 , b s(q) ) ∈ Rm r+1 m s(q) since s(q) < q. We know that (am r+1 , am q ) ∈ Rm r+1 mq from Equation (2), and that (am r+1 , bq) / ∈ Rm r+1 mq by definition of q. We know that (bq, b s(q) ) ∈ Rm q m s(q) and (am q , b s(q) ) / ∈ Rm q m s(q) from Hq. By arc consistency, ∃br+1 ∈ D(xm r+1 ) such that (br+1, bq) ∈ Rm r+1 mq . We then have the situation illustrated in Figure 6 . As above, from the absence of pattern EMC, we can deduce that br+1 > am r+1 . We thus have Hr+1 (with s(r +1) = q and p(r + 1) = s(q)). New tractable classes solved by arc consistency Case (2) j < m1: Consider the subproblem I of I on the subset of variables {x1, x2, . . . , xm 1 −1} ∪ {x k }. Since xm 1 does not belong to the set of variables of I , this instance has size strictly less than n, and hence by our inductive hypothesis has a solution. The values of ai may differ between I and I . However, we can see from its definition given in Equation (1), that the value of ai depends uniquely on the subproblem on previous variables {x1, . . . , xi−1}. Showing the dependence on the instance by a superscript, we thus have a I i = a I i (i = 1, . . . , m1 − 1) although a I k may (and, in fact, does) differ from a I k . By our inductive hypothesis, a1, . . . , am 1 −1, a I k is a solution to I . Setting b0 = a I k , it follows that (ai, b0) ∈ R ik for 1 ≤ i < m1. In particular, since j < m1, we have (aj, b0) ∈ R jk . Now a I k ≤ a I k = b0, since I is a subinstance of I (and so, from Equation (1), a I k is the minimum of a superset over which a I k is a minimum). Thus a k = a I k < b0, since (aj, b0) ∈ R jk and (aj, a k ) / ∈ R jk . By arc consistency, ∃b1 ∈ D(xm 1 ) such that (b1, b0) ∈ R m 1 k . As in case (1), we have the situation illustrated in Figure 4 for h = 1. Since the pattern EMC does not occur in I, we must have b1 > am 1 . New tractable classes solved by arc consistency Consider the hypothesis Hr stated in case (1) and illustrated in Figure 5 . We have just shown that H1 holds (with s(1) = 0 and p(1) = j). We now show, for 1 ≤ r < t, that (H1 ∧ . . . ∧ Hr) ⇒ Hr+1. New tractable classes solved by arc consistency As in case (1), we know that (am r+1 , am r ) ∈ Rm r+1 mr and (am r+1 , br) / ∈ Rm r+1 mr . Let q ∈ {0, . . . , r} be minimal such that (am r+1 , bq) / ∈ Rm r+1 mq . We have seen above that (am r+1 , b0) ∈ R m r+1 k (since xm r+1 , xm 0 are assigned, respectively, the values am r+1 , b0 in a solution to I ). Therefore, we can deduce that q > 0. Therefore H1 ∧ . . . ∧ Hr implies that Hq holds. By minimality of k, and since mq < m0 = k, we know that (am r+1 , am q ) ∈ Rm r+1 mq . As in case (1), by minimality of q, we know that (am r+1 , b s(q) ) ∈ Rm r+1 m s(q) . By arc consistency, ∃br+1 ∈ D(xm r+1 ) such that (br+1, bq) ∈ Rm r+1 mq . We thus have the situation illustrated in Figure 6 . Again, from the absence of pattern EMC, we can deduce that br+1 > am r+1 . We thus again have Hr+1 with s(r + 1) = q and p(r + 1) = s(q). New tractable classes solved by arc consistency Thus, by induction on r, we have shown in both cases that Ht holds. But recall that mt = 1 and that a1 was chosen to the maximal element of D(x1) and hence bt ∈ D(x1) such that bt > a1. This contradiction shows that a1, . . . , an is a solution, as claimed. New tractable classes solved by arc consistency The next two patterns we study in this section, shown in Figure 7 and Figure 8 , are similar to EMC but the three patterns are incomparable (in the sense that none occurs in another) due to the different orders on the three variables. New tractable classes solved by arc consistency Theorem 2 AC is a decision procedure for CSP SP (BT X) where BTX is the pattern shown in Figure 7 . New tractable classes solved by arc consistency Theorem 3 AC is a decision procedure for CSP SP (BT I) where BTI is the pattern shown in Figure 8 . We conclude this section with a pattern which is essentially different from the patterns EMC, BTX, and BTI, since it includes two negative edges that meet but has no domain or variable order, and whose tractability was previously unknown (Escamocher 2014) . New tractable classes solved by arc consistency Theorem 4 AC is a decision procedure for CSP SP (LX) where LX is the pattern shown in Figure 9 . New tractable classes solved by arc consistency Proof: Since establishing arc consistency only eliminates domain elements, and hence cannot introduce the pattern, we only need to show that every arc-consistent instance I ∈ CSP SP (LX) has a solution. In fact we will show a stronger result by proving that the hypothesis Hn, below, holds for all n ≥ 1. New tractable classes solved by arc consistency Hn: for all arc-consistent instances I = X, D, A, cpt ∈ CSP SP (LX) with |X| = n, ∀xi ∈ X, ∀a ∈ D(xi), I has a solution s such that s(xi) = a. New tractable classes solved by arc consistency Trivially, H1 holds. Suppose that Hn−1 holds where n > 1. We will show that this implies Hn, which will complete the proof by induction. New tractable classes solved by arc consistency Consider an arc-consistent instance I = X, D, A, cpt from CSP SP (LX) with X = {x1, . . . , xn} and let a ∈ D(xi) where 1 ≤ i ≤ n. Let In−1 denote the subproblem of I on variables X \ {xi}. For any solution s of In−1, we denote by CV ( xi, a , s) the set of variables in X \ {xi} on which s is compatible with the unary assignment xi, a , i.e. CV ( xi, a , s) = {xj ∈ X \ {xi} | (a, s(xj)) ∈ Rij} Consider two distinct solutions s, s to In−1. If we have xj ∈ CV ( xi, a , s) \ CV ( xi, a , s ) and x k ∈ CV ( xi, a , s ) \ CV ( xi, a , s), then the pattern LX occurs in I under the mapping Figure 9 ). Since LX does not occur in I, we can deduce that the sets CV ( xi, a , s), as s varies over all solutions to In−1, form a nested family of sets. Let sa be a solution to In−1 such that CV ( xi, a , sa) is maximal for inclusion. New tractable classes solved by arc consistency Consider any xj ∈ X \ {xi}. By arc consistency, ∃b ∈ D(xj) such that (a, b) ∈ Rij. By our inductive hypothesis Hn−1, there is a solution s to In−1 such that s(xj) = b. Since (a, s(xj)) = (a, b) ∈ Rij, we have xj ∈ CV ( xi, a , s). By maximality of sa, this implies xj ∈ CV ( xi, a , sa), i.e. (a, sa(xj)) ∈ Rij. Since this is true for any xj ∈ X \ {xi}, we can deduce that sa can be extended to a solution to I (which assigns a to xi) by simply adding the assignment xi, a to sa. Recognition problem for unknown orders For an unordered pattern P of size k, checking for (the nonoccurrence of) P in a CSP instance I is solvable in time O(|I| k ) by simple exhaustive search. Consequently, checking for (the nonoccurrence of) unordered patterns of constant size is solvable in polynomial time. However, the situation is less obvious for ordered patterns since we have to test all possible orderings of I. Recognition problem for unknown orders The following result was shown in (Cooper et al. 2010b) . Recognition problem for unknown orders Theorem 5 Given a binary CSP instance I with a fixed total order on the domain, there is a polynomial-time algorithm to find a total variable ordering such that BTP does not occur in I (or to determine that no such ordering exists). Recognition problem for unknown orders We show that the same result holds for the other three ordered patterns studied in this paper, namely BTI, BTX, and EMC. Recognition problem for unknown orders Theorem 6 Given a binary CSP instance I with a fixed total order on the domain and a pattern P ∈ {BTI, BTX, EMC}, there is a polynomial-time algorithm to find a total variable ordering such that P does not occur in I (or to determine that no such ordering exists). Recognition problem for unknown orders Proof: We give a proof only for BTX as the same idea works for the other two patterns as well. Given a binary CSP instance I with n variables x1, . . . , xn, we define an associated CSP instance ΠI that has a solution precisely when there exists a suitable variable ordering for I. To construct ΠI , let O1, . . . , On be variables taking values in {1, . . . , n} representing positions in the ordering. We impose the ternary constraint Oi > max(Oj, O k ) for all triples of variables xi, xj, x k in I such that the BTX pattern occurs for some α, β ∈ D(xi) with α > β, ∈ D(xj), and γ, δ ∈ D(x k ) when the variables are ordered xi < xj, x k . The instance ΠI has a solution precisely if there is an ordering of the variables x1, . . . , xn of I for which BTX does not occur. Note that if the solution obtained represents a partial order (i.e. if Oi and Oj are assigned the same value for some i = j), then it can be extended to a total order which still satisfies all the constraints by arbitrarily choosing the order of those Oi's that are assigned the same value. This reduction is polynomial in the size of I. We now show that all constraints in ΠI are ternary max-closed and thus ΠI can be solved in polynomial time (Jeavons and Cooper 1995) . Let p1, q1, r1 and p2, q2, r2 satisfy any constraint in ΠI . Then p1 > max(q1, r1) and p2 > max(q2, r2), and thus max(p1, p2) > max(max(q1, r1), max(q2, r2)) = max(max(q1, q2), max(r1, r2)). Consequently, max(p1, p2), max(q1, q2), max(r1, r2) also satisfies the constraint. We can deduce that all constraints in ΠI are max-closed. Recognition problem for unknown orders Using the same technique, we can also show the following. Recognition problem for unknown orders Theorem 7 Given a binary CSP instance I with a fixed total variable order and a pattern P ∈ {BTI, BTX}, there is a polynomialtime algorithm to find a total domain ordering such that P does not occur in I (or determine that no such ordering exists). Recognition problem for unknown orders It is known that determining a domain order for which MC does not occur is NP-hard (Green and Cohen 2008) . Not surprisingly, for EMC when the domain order is not known, detection becomes NP-hard. For the case of BTX and BTI, if neither the domain nor variable order is known, finding orders for which the pattern does not occur is again NP-hard. Recognition problem for unknown orders Theorem 8 For the pattern EMC, even for a fixed total variable order of an arc-consistent binary CSP instance I, it is NP-hard to find a total domain ordering of I such that the pattern does not occur in I. For patterns BTX and BTI, it is NP-hard to find total variable and domain orderings of an arc-consistent binary CSP instance I such that the pattern does not occur in I. Characterisation of patterns solved by AC Instances not solved by arc consistency We first give a set of instances, each of which is arc consistent and has no solution. If for any of these instances I, we have I ∈ Instances not solved by arc consistency @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ CSP SP (P ), then this constitutes a proof, by Lemma 4, that pattern P is not solved by arc consistency. For simplicity of presentation, in each of the following instances, we suppose the variable order given by xi < xj if i < j. @ @ h h h h h h h h h h h h h h h h h h • IK4 (shown in Figure 10 ) is composed of four variables with domains D(xi) = {1, 2, 3} (i = 1, 2, 3, 4), and the following constraints: (xi = 1) ∨ (xj = 3) ((i, j) = (1, 2), (2, 3), (3, 4), (4, 1)) and (xi = 2) ∨ (xj = 2) ((i, j) = (1, 3), (2, 4)). @ @ h h h h h h h h h h h h h h h h h h • I4 is composed of four variables with domains D(x0) = {1, 2, 3}, D(xi) = {0, 1} (i = 1, 2, 3), and the following constraints: xi ∨ xj (1 ≤ i < j ≤ 3) and (x0 = i) ∨ xi (i = 1, 2, 3). @ @ h h h h h h h h h h h h h h h h h h is composed of five Boolean variables and the following constraints: x1 ∨x2, x3 ∨x4, x1 ∨x5, x2 ∨x5, x3 ∨x5, x4 ∨x5. • I5 is composed of five variables with domains D(wi) = {0, 1} (i = 1, 2, 3), D(xi) = {1, 2, 3}, and the constraints: wi ∨ (x1 = i) (i = 1, 2, 3) and wi ∨ (x2 = i) (i = 1, 2, 3). In this instance the variable order is w1 < w2 < x1 < x2 < x3. @ @ h h h h h h h h h h h h h h h h h h is composed of six Boolean variables and the following constraints: x1 ∨x2, x1 ∨x3, x1 ∨x4, x3 ∨x4, x2 ∨x5, x2 ∨x6, x5 ∨ x6. Figure 11 ) is composed of four Boolean variables and the following constraints: x1 ∨x2, x3 ∨x4 and xi ∨xj (for (i, j) = (1, 3), (1, 4), (2, 3), (2, 4)). @ @ h h h h h h h h h h h h h h h h h h is composed of three Boolean variables and the three inequality constraints: xi = xj (1 ≤ i < j ≤ 3). @ @ h h h h h h h h h h h h h h h h h h We illustrate two of these instances in Figure 10 and Figure 11 . Figure 12(a) is a pattern which does not occur in the instance IK4 ( Figure 10) . Similarly, Figure 12(b) is a pattern which does not occur in the instance I4 and the pattern in Figure 12 (c) does not occur in instance I SAT 2∆ . Figure 12(d) , (e) and (f) are three patterns which do not occur in the instance I5. The pattern (known as T 1) shown in Figure 12(d) is, in fact, a tractable pattern (Cooper and Escamocher 2015) , but the fact that it does not occur in I5 (an arc-consistent instance which has no solution) shows that arc consistency is not a decision procedure for CSP SP (T 1). This instance was constructed using certain known properties of the pattern T 1 (Escamocher 2014) . @ @ h h h h h h h h h h h h h h h h h h It can easily be verified that the three patterns Figure 12 (g), (h), (i) do not occur in I SAT 6 . Similarly, the four patterns in Figure 12(j) ,(k),(l),(m) do not occur in the instance I SAT K4 (Figure 11 ). The instance I 2COL 3 is the problem of colouring a complete graph on three vertices with only two colours. It is arc consistent but clearly has no solution. It is easy to verify that none of the six patterns in Figure 12 , then it is not AC-solvable. Let P be any of the patterns shown in Figure 12 . By Lemma 5, any pattern Q in which P occurs is not AC-solvable. 6 By the pattern in Figure 12(g) , an simple AC-solvable pattern cannot contain two negative edges between the same pair of variables. Since instance I 2COL 3 contains only three variables and instance I5 contains no triple of variables which have a negative edge between each pair of variables, an AC-solvable pattern can contain at most three variables and at most two negative edges. Thus to identify simple AC-solvable patterns we only need to consider patterns on at most three variables, at most two points per variable and with none, one or two negative edges. Furthermore, in the case of two negative edges these negative edges cannot be between the same pair of variables. Characterising AC-solvable unordered patterns In this subsection, we consider only patterns P that have no associated structure (i.e. with <X = <D = ∅). We prove the following characterisation of unstructured AC-solvable patterns. Characterising AC-solvable unordered patterns Theorem 9 If P is an simple unordered pattern, then P is ACsolvable if and only if P occurs in the pattern LX (Figure 9 ) or in the pattern unordered(BTP). Characterising AC-solvable unordered patterns Proof sketch: Let P be an simple unordered pattern. By exhaustive search we can deduce that either (1) P occurs in LX or unordered(BTP), or (2) at least one of the following patterns occurs in P : Figure 12(a) , (b), (d), (n), (p), (q), (s). In case (1), by Lemma 1, Lemma 2, Lemma 3, Theorem 4 and the fact that BTP is known to be AC-solvable (Cooper et al. 2010b) , it follows that P is ACsolvable. In case (2), since all patterns in Figure 12 are not ACsolvable, by Lemma 5, P is not AC-solvable. Characterising AC-solvable variable-ordered patterns In this subsection we consider simple patterns P which have no domain order, but do have a partial order on the variables. We first require the following lemma. Characterising AC-solvable variable-ordered patterns Lemma 8 If P < is a pattern whose only structure is a partial order on its variables and P − = unordered(P < ), then Characterising AC-solvable variable-ordered patterns Proof: The property of being simple is independent of any variable order, hence P < is simple if and only if P − is simple. By Lemma 3, P − occurs in P < . The fact that P < is AC-solvable only if P − is AC-solvable then follows from Lemma 5. Characterising AC-solvable variable-ordered patterns Recall pattern LX < from Example 7 that is obtained from the pattern LX (Figure 9 ) by adding the partial variable order y < z. Characterising AC-solvable variable-ordered patterns Lemma 8 allows us to give the following characterisation of variable-ordered AC-solvable patterns. Characterising AC-solvable variable-ordered patterns Theorem 10 If P is an simple pattern whose only structure is a partial order on its variables, then P is AC-solvable if and only if P occurs in the pattern LX < , the pattern BTP vo (Figure 2 ) or the pattern invVar(BTP vo ). Characterising AC-solvable variable-ordered patterns Proof sketch: By Lemma 8 and Theorem 9, we only need to consider patterns occurring in LX or unordered(BTP) to which we add a partial order on the variables. Let P be such a pattern. By exhaustive search we can show that either (1) P occurs in LX < , BTP vo or invVar(BTP vo ), or (2) at least one of the patterns in Figure 12 (e), (f) occurs in P . In case (1), P is AC-solvable, since LX < and BTP vo are equivalent to the AC-solvable patterns LX and BTP, respectively. In case (2), P is not AC-solvable, by Lemma 5, since the patterns in Figure 12 are not AC-solvable. Characterising AC-solvable domain-ordered patterns In this subsection we consider simple patterns P with a partial order on domains but no ordering on the variables. Characterising AC-solvable domain-ordered patterns Let EMC − be the no-variable-order version of the pattern EMC depicted in Figure 3 . Characterising AC-solvable domain-ordered patterns We prove the following characterisation of domain-ordered ACsolvable patterns. Characterising AC-solvable domain-ordered patterns Theorem 11 If P is an simple pattern whose only structure is a partial order on its domains,
{'paper_id': '191061', 'title': 'The Power of Arc Consistency for CSPs Defined by Partially-Ordered Forbidden Patterns', 's2_url': 'https://api.semanticscholar.org/CorpusID:191061', 'source': 'S2ORC'}