# the_metaproblem_for_conservative_maltsev_constraints__db0cfa1e.pdf

The Meta-Problem for Conservative Mal tsev Constraints

Cl ement Carbonnel

LAAS-CNRS University of Toulouse, INP Toulouse, France carbonnel@laas.fr

In the algebraic approach to CSP (Constraint Satisfaction Problem), the complexity of constraint languages is studied using closure operations called polymorphisms. Many of these operations are known to induce tractability of any language they preserve. We focus on the meta-problem: given a language Γ, decide if Γ has a polymorphism with nice properties. We design an algorithm that decides in polynomial-time if a constraint language has a conservative Mal tsev polymorphism, and outputs one if one exists. As a corollary we obtain that the class of conservative Mal tsev constraints is uniformly tractable, and we conjecture that this result remains true in the non-conservative case.

1 Introduction The complexity of constraint satisfaction problems is a very active and fruitful research area. In particular, the study of CSP over fixed constraint languages has attracted considerable interest since it was conjectured that for every finite constraint language Γ, CSP(Γ) is either in P or NP-hard (the Feder-Vardi Dichotomy Conjecture) (Feder and Vardi 1998). The most remarkable achievements to date include a characterization of languages that can be solved by local consistency methods (Barto and Kozik 2014) or Gaussian-like algorithms (Idziak et al. 2007), and a proof of the Dichotomy Conjecture for conservative languages (languages with all possible unary relations over the domain) (Bulatov 2003). These results use the algebraic approach to CSP: every language Γ can be associated with a set of closure operations, called polymorphisms, which have been shown to entirely determine the complexity of CSP(Γ) (Jeavons, Cohen, and Gyssens 1997). Given an operation f : Dk D, a language Γ over the domain D admits f as a polymorphism if every constraint relation R Γ is closed under componentwise application of f. For example, the affine relation x+y +z = c is closed under the polymorphism f(x1, x2, x3) = x1 x2+x3, since x1 + y1 + z1 = c, x2 + y2 + z2 = c, x3 + y3 + z3 = c imply that f(x1, x2, x3) + f(y1, y2, y3) + f(x3, y3, z3) = (x1 x2 + x3) + (y1 y2 + y3) + (z1 z2 + z3) = c.

supported by ANR Project ANR-10-BLAN-0210. Copyright c 2016, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

A number of sufficient conditions for tractability have been identified this way; for instance, CSP(Γ) is solved by enforcing generalized arc-consistency (GAC) if Γ has a semilattice polymorphism (Jeavons, Cohen, and Gyssens 1997). Each sufficient condition defines a tractable class, that is, a set T of languages such that Γ T, CSP(Γ) is in P. There are some desirable properties that good tractable classes can be expected to have. First, we know that there exists a polynomial-time algorithm for each fixed Γ T, but there is no guarantee that there exists one polynomial-time algorithm that solves every CSP(Γ), Γ T. This can be formalized as a promise problem: if CSP(T) is CSP together with the promise that the instance is over a language in T, is it true that CSP(T) P? If the answer is yes, we say that T is uniformly tractable (or equivalently that T uniformizes (Kolaitis and Vardi 2000)). We shall illustrate this notion with an example. Consider the tractable class Tc of all languages Γ such that CSP(Γ) can be solved by enforcing strong k-consistency, where k only depends on Γ. Since there is no bound on k in the definition of Tc, it is not clear that Tc is uniformly tractable. However, a powerful result by Bulatov implies that enforcing a form of consistency called (2, 3)-minimality suffices to solve CSP(Γ) for each Γ Tc (Bulatov 2010). Enforcing (2, 3)-minimality is polynomial-time, so Tc is uniformly tractable. Even if the class is uniformly tractable, one problem remains: how hard is it to decide if a given language Γ is in T? This is the meta-problem for T. In its full generality, the meta-problem has no restriction on the input language. In particular, the domain size is not assumed to be bounded. In the worst case the meta-problem is not necessarily decidable, but in practice it is often in NP. If the class is defined by the existence of polymorphisms satisfying a certain set of identities (which is usually the case), the meta-problem is a polymorphism detection problem. For instance, the class of languages that admit a semilattice polymorphism is uniformly tractable since it is solved by GAC, but the metaproblem is NP-complete (Green and Cohen 2008). Beyond pure academic interest, the main reason for investigating the complexity of meta-problems concerns generalpurpose solvers. It is great to know that languages with a nice polymorphism can be solved efficiently, but this information is virtually useless for practical constraint solvers if

Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence (AAAI-16)

they cannot decide quickly if the language of the instance they are trying to solve has the desired polymorphism. Furthermore, it was observed that constraint solvers may perform poorly even on instances that are theoretically very easy (Petke and Jeavons 2009), which suggests that spending some time analyzing the instance before starting search could be beneficial. Beyond preprocessing uses, a very efficient detection algorithm could be exploited in the framework of backdoors, which aims to provide performance improvements even if only a fraction of the constraints have a nice polymorphism (Williams, Gomes, and Selman 2003). In this setting, conservative polymorphisms are of special interest (Bessiere et al. 2013). Sometimes, the complexity of the meta-problem is strongly related to the uniform tractability question. This is true for the tractable class TMal of all languages that admit a Mal tsev polymorphism, which include as particular cases the languages whose relations are linear equations over a field (Bulatov 2002). The solution algorithm resembles Gaussian elimination, in that it starts from an instance without any constraint and then adds the constraints one by one while maintaining at all times a polynomial-sized representation of the solution set (Bulatov and Dalmau 2006)(Dyer and Richerby 2013). This algorithm remains polynomial time even if the domain size or the number of tuples are not fixed, but it does not entail uniform tractability because it assumes that the Mal tsev polymorphism is known. Since there are roughly dd3 possible Mal tsev operations over a domain of size d and it is possible that only one of them is a polymorphism of the language, an exhaustive approach is not satisfying. However, should a polynomial-time algorithm that outputs a Mal tsev polymorphism if one exists be engineered, we could interface it with the state-of-the-art solution algorithm and prove uniform tractability of TMal. But then, this polymorphism detection algorithm would also prove that the meta-problem is in P. This paper builds around the observation that TMal is likely to have an easy meta-problem and be uniformly tractable. Although we cannot prove this claim in its full generality, we present a proof for the restricted case of conservative Mal tsev polymorphisms. This extends previous results showing that conservative Mal tsev polymorphisms can be detected in polynomial time in digraphs (Carvalho et al. 2011) and binary relational structures (Bessiere et al. 2013). As a byproduct, we obtain a greatly improved algorithm for detecting conservative majority polymorphisms, which generalise 2SAT and connected row-convex constraints. Besides being a first step towards proving the uniform tractability of Mal tsev constraints, our result for the conservative case is interesting in its own right. The tractable class of languages having a conservative Mal tsev polymorphism has seen little pratical use, but is of great theoretical importance. For instance, conservative Mal tsev polymorphisms are one of the main ingredients in Libor Barto s proof of the conservative Dichotomy Conjecture (Barto 2011). Moreover, the existence of a conservative Mal tsev polymorphism is a necessary condition for the tractability of CCSP(Γ), a variant of CSP(Γ) in which global cardinality constraints

are allowed in addition to the relations of Γ (Bulatov and Marx 2010). Examples of conservative Mal tsev operations include extreme value functions, which map any triplet {x, y, z} of natural numbers to α {x, y, z} such that |α median(x, y, z)| is maximum.

2 Preliminaries CSP. A Constraint Satisfaction Problem (CSP) is a triple (X,D,C) where X is a set of variables, D is a finite set of values, and C is a set of constraints. A constraint C of arity r is a pair (S(C), R(C)) where S(C) X r is the scope of C and R(C) Dr is the relation of C. Note that R(.) and S(.) can be seen as operators that return the relation and scope of a constraint. A solution of I is an assignment φ : X D such that C C, φ(S(C)) R(C), and the goal is to decide if I has a solution. A constraint language is a set of relations, and the language of a CSP instance I is the set ΓI = {R(C) | C C}. Given a fixed constraint language Γ, CSP(Γ) is the set of all instances I such that ΓI Γ. We assume that all relations are given in extension (i.e. as lists of tuples). Polymorphisms. An operation f : D Dk is a polymorphism of a language Γ over D if for all R Γ of arity r and t1, . . . , tk R, < f(t1[1], . . . , tk[1]), . . ., f(t1[r], . . . , tk[r]) > R. The set of all polymorphisms of Γ is denoted by Pol(Γ) and constitutes an operational clone, that is, a set of operations closed under composition that contains all projections (Jeavons, Cohen, and Gyssens 1997). It has been shown that the complexity of CSP(Γ) is entirely determined by Pol(Γ) (Jeavons, Cohen, and Gyssens 1997). An operation f : D Dk is conservative if f(x1, . . . , xk) {x1, . . . , xk} for all x1, . . . , xk D, Mal tsev if it is ternary and x, y D, f(x, x, y) = f(y, x, x) = y, and majority if it is ternary and x, y D, f(x, x, y) = f(x, y, x) = f(y, x, x) = x. Tools. The most useful tool used to design polymorphism detection algorithms is the indicator problem. Formally, given an integer k and a finite constraint language Γ, the indicator problem of order k of Γ is a CSP instance IP k(Γ) with one variable xv1,...,vk for every k-tuple (v1, . . . , vk) of elements from D. Then, for each R Γ of arity r and t1, . . . , tk R, IP k(Γ) contains a constraint CR t1,...,tk with scope (xt1[1],...tk[1], . . . , xt1[r],...,tk[r]) and relation R. Going back to the definition of a polymorphism, it follows that an operation f of arity k is a polymorphism of Γ if and only if xv1,...,vk f(v1, . . . , vk) is a solution of IP k(Γ). If we are only looking for polymorphisms with special properties, sometimes the solution set of IPk(Γ) can be restricted to exactly those polymorphisms. For instance, if k = 3 adding the unary constraints xv1,v1,v2 {v1}, xv1,v2,v1 {v1}, xv2,v1,v1 {v1} for every v1, v2 D will ensure that every solution of this modified indicator problem IPmaj(Γ) is a majority polymorphism. This type of restriction is sometimes not possible without increasing exponentially the size of the indicator problem (e.g. semilattices). It was first observed in (Feder and Vardi 1998) that the language of IPmaj(Γ) is Γ plus unary relations with a single tuple, and thus has a majority polymorphism if and only if IPmaj(Γ)

has a solution. Furthermore, by the properties of majority polymorphisms it follows that if IPmaj(Γ) has a solution, then it can be solved backtrack-free by applying singleton arc-consistency at each node of the search tree (Chen, Dalmau, and Grußien 2013). The standard algorithm for detecting majority polymorphisms starts by building IPmaj(Γ) and then solves it by a standard search, maintaining SAC at each node. If the algorithm backtracks, we can conclude that Γ has no majority polymorphism, so the whole procedure is polynomial-time. This approach has been used for several other tractable classes (Barto 2015)(Feder and Vardi 1998). However, this kind of detection algorithm requires the existence of a uniform algorithm for the tractable class, which is not known for several polymorphisms including (conservative) Mal tsev polymorphisms. In this paper we introduce a different technique, based on a detailed analysis of the structure of the indicator problem.

3 First observation Recall that the existence of a uniform algorithm for Mal tsev constraints is equivalent to the tractability of the problem CSP(TMal), where we only have the promise that the language of the instance has a Mal tsev polymorphism. The complexity of this problem is open, but is it easy to see that the following is true.

Observation 1. CSP(TMal) NP co NP.

Proof. Membership in NP follows from that of the general CSP. For membership in co NP, a Mal tsev polymorphism f of the constraint language is a certificate: with the knowledge of f, the algorithm from (Dyer and Richerby 2013) provides a way to check in polynomial time that the instance has no solution.

Unless NP = co NP, this observation rules out the possibility that this problem is NP-hard (Goldreich 2010). Besides, examples of NP co NP problems that are not believed to be in P are quite rare, so we regard this observation as evidence that Mal tsev constraints may have a uniform algorithm. Using the same kind of reasoning as for majority polymorphisms, it would follow that Mal tsev polymorphisms can be detected in polynomial time. The next section will provide additional evidence by proving that conservative Mal tsev constraints are uniformly tractable. We note that this observation also applies to the larger tractable class of languages having a k-edge polymorphism (for a fixed k) by using the algorithm of (Idziak et al. 2007) for membership in co NP. However, for the sake of simplicity we shall focus on the case k = 2, which corresponds to Mal tsev polymorphisms.

4 Conservative Mal tsev constraints In this section, we show that the existence of a conservative Mal tsev polymorphism can be decided in polynomial time. The outline of the proof is as follows. We first reduce the problem to that of finding a conservative minority polymorphism (i.e. a ternary polymorphism m such that x, y, m(x, x, y) = m(x, y, x) = m(y, x, x) = y). Then, we

show that enforcing arc-consistency on the indicator problem associated with conservative minority polymorphisms leaves an extremely well-structured instance, and a simple reduction rule allows us to eliminate every variable whose domain contains more than two values. The residual instance is then shown to be equivalent to a system of linear equations over GF(2), and can be solved by Gaussian elimination.

Lemma 1. Let F be an operational clone. F contains a conservative Mal tsev operation if and only if it contains a conservative minority operation.

Proof. Every minority operation is a Mal tsev operation, hence one implication is trivial. Suppose that F contains a conservative Mal tsev operation m, and let

f(x, y, z) = m(z, m(y, m(x, z, y), x), m(x, z, y))

This operation belongs to F because F is a clone, and is conservative since m is conservative. Furthermore, for every a, b we have

f(a, b, a) = m(a, m(b, m(a, a, b), a), m(a, a, b)) = b f(b, a, a) = m(a, m(a, m(b, a, a), b), m(b, a, a)) = b

and it is fairly straightforward to see that f(a, a, b) = m(b, m(a, m(a, b, a), a), m(a, b, a)) is always equal to b, whether m(a, b, a) = b or m(a, b, a) = a. Hence, f is a minority operation of F.

Although this lemma may be known to some, it appears to have never been pointed out in the literature. The closest results we could find were that digraphs with a conservative Mal tsev polymorphisms also have a conservative minority polymorphism (Carvalho et al. 2011) and constraint languages with both a conservative majority and a conservative Mal tsev polymorphism also have a conservative minority polymorphism (Bulatov and Marx 2010). In our case, this lemma is crucial, since the indicator problem corresponding to conservative minority polymorphisms has interesting (i.e., algorithmically exploitable) properties that its counterpart for Mal tsev polymorphisms does not have. Given a language Γ, we denote by IPcmin(Γ) the indicator problem of order 3 of Γ with the additional constraints xv1,v1,v2 {v2}, xv1,v2,v1 {v2}, xv2,v1,v1 {v2} for every v1, v2 D and xv1,v2,v3 {v1, v2, v3} for every v1, v2, v3 D. By construction, the solutions of IPcmin(Γ) are exactly the conservative minority polymorphisms of Γ. Given a constraint C = (S, R) and S S, we denote by C[S ] the projection of C onto S . For our structural analysis we will assume that for every R Γ, IPcmin(Γ) also contains a constraint CR t 1,t 2,t 3 for every projection R of R

and t 1, t 2, t 3 R . These additional constraints are only needed to facilitate our analysis and will not be required by the algorithm. In a generalized arc-consistent instance, the domain D(x) of a variable x is the set of values for x that have supports in every constraint whose scope contains x. For the remainder of the paper, we will assume that GAC has been enforced on

IPcmin(Γ). The following observation describes an immediate but very important property that will be used repeatedly in our proofs.

Observation 2. If CR t1,t2,t3 = (R, S) is a constraint in IPcmin(Γ) and t, t , t R, then R(CR t,t ,t ) R.

Proof. Let CR t,t ,t = (R , S ), and |S| = |S | = r. Before GAC was enforced, both CR t1,t2,t3 and CR t,t ,t had R as relation. Thus, by definition of generalized arcconsistency, we have R = R (πx SD(x)) and R = R (πx S D(x)). However, since t, t , t R, the conservativity constraints ensure that for each i = 1..r, D(S [i]) D(S[i]). Therefore, R R.

Throughout the paper we will treat elements of a scope S as occurences of variables, and not simply variables. For example, given x S, the restricted scope S\x removes the occurence x from S, but not every occurence of the variable represented by x. A constraint C = (S, R) is functional in x S if for every valid assignment t of S\x there is at most one value d D such that (S\x t, x d) is an assignment to S that satisfies C. Finally, if two relations R and R differ only by a permutation of their columns, we write R R . The proof of the next lemma gives a simple example of the use we will make of Observation 2. We remind the reader that if C = CR t1,t2,t3 is a constraint of IPcmin(Γ), the kth variable in its scope is xt1[k],t2[k],t3[k]. Therefore, if t1[k] = t2[k], the unary constraints will ensure that xt1[k],t2[k],t3[k] is ground (i.e. has a singleton domain) with value t3[k].

Lemma 2. Let C = (R, S) be a constraint in IPcmin(Γ), and let x S. Either C is functional in x, or R R(C[S\x]) D(x).

Proof. Let C = CR t1,t2,t3 and x = xv1,v2,v3. Without loss of generality, we assume that x occurs last in S. First, suppose that there exists t R(C[S\x]) such that (t, vk) R(C) for every vk D(x). We will show that every tuple must have the same property as t. Let t R(C[S\x]) be such that (t , vα) R(C) but (t , vβ) / R(C) for some {vα, vβ} D(x). Then, because of the unary constraints, the constraint CR (t,vα),(t,vβ),(t ,vα) has only ground variables in its scope, and its only possible support is (t , vβ). By Observation 2, R(CR (t,vα),(t,vβ),(t ,vα)) R(C) and hence (t , vβ) R(C), a contradiction. Therefore, such a partial tuple t cannot exist and R R(C[S\x]) D(x). Now, suppose that D(x) = {v1, v2, v3} and there exists t R(C[S\x]) such that (t, vk) R(C) for exactly two indices k, say 1 and 2. Since C is arc-consistent, there exists t such that (t , v3) R(C). However, the scope of constraint CR (t,v1),(t,v2),(t ,v3) contains only ground variables and x; therefore R(CR (t,v1),(t,v2),(t ,v3)) contains the tuple (t , vk) for all k {1, 2, 3}. By Observation 2 we have R(CR (t,v1),(t,v2),(t ,v3)) R(C), and the partial tuple t brings us back to the first case.

If no tuples satisfy either of the above two conditions, C is functional in x.

The key observation in our proof will be that variables with domain size 1 or 2 have very limited interactions with variables with domain size 3 once arc-consistency has been enforced. Given a constraint C in IPcmin(Γ), we denote by S|1,2(C) the restriction of S to variables with domain size 1 or 2, and by S|3(C) the restriction of S to variables with domain size 3.

Lemma 3. Let C be a constraint in IPcmin(Γ) and x S|3(C). R(C[S|1,2(C) x]) R(C[S|1,2(C)]) D(x).

Proof. Let C1 = C[S|1,2(C)] = (R1, S1), C2 = C[S|1,2(C) x] = (R2, S2) and assume that x = xv1,v2,v3 occurs last in the scope of C2. By Lemma 2, either R2 = R1 D(x) or C2 is functional in x. If it is functional, then by GAC there exist t, t , t R1 such that R2 contains (t, v1), (t , v2) and (t , v3). Then, the scope of C = CR (t,v1),(t ,v2),(t ,v3) has only ground variables (those corresponding to S|1,2(C)) plus xv1,v2,v3. Therefore, there exists t such that R(C ) contains (t , v1), (t , v2) and (t , v3). By Observation 2, R(C ) R2 and C2 is not functional in x, a contradiction.

Lemma 3 only deals with constraints whose scope contains exactly one variable with domain size 3. Unfortunately, for k variables it is not completely true that R(C[S|1,2(C) {x1, . . . , xk}]) R(C[S|1,2(C)]) D(x1) . . . D(xk). Let xv1 1,v1 2,v1 3, . . . , xvk 1 ,vk 2 ,vk 3 be k variables of the indicator problem. The index-equality constraint between these variables has three satisfying assignments: (v1 1, . . . , vk 1), (v1 2, . . . , vk 2) and (v1 3, . . . , vk 3). The next Proposition is the keystone of our proof, and gives the correct generalization of Lemma 3 to an arbitrary number of variables with domain size 3.

Proposition 1. Let C be a constraint in IPcmin(Γ). There exists n 0 and a set of constraints C , C1, . . . , Cn such that

where the scope of C is S(C), the constraints Ci are (possibly unary) index-equalities whose scope are disjoint and cover S|3(C), and

R(C ) R(C[S|1,2(C)]) Πx S|3(C)D(x)

Proof. We proceed by induction on the size of S|3(C). Let k > 0 and suppose that Proposition 1 is true for all constraints C such that |S|3(C )| k. Let C = CR t1,t2,t3 = (S, R) be a constraint with |S|3(C)| = k + 1, and x S|3(C). By Lemma 2, either C is functional in x or R(C) =

R(C[S\x]) D(x). In the latter case, C satisfies Proposition 1 by induction. Therefore, we shall assume that C is functional in x. By induction, we know that C[S\x] = C

i=1..n Ci. Let y {1..n} and Y = S(Cy). Let vi, i = 1, 2, 3 be the three possible assignments to Y . We assume without loss of generality that x = xu1,u2,u3 (hence, D(x) = {u1, u2, u3}) and (Y, x) are the last variables in S. Let t R(C[S\{Y, x}]), and define φt : D(Y ) D(x) such that φt(v) = {u D(x) | (t, v, u) R(C)}. We distinguish three cases.

1. φt has range {ui, uj} for some i = j. One of these two values, say ui, has a preimage of size 2. Let {vp, vs} = φ 1 t ({ui}), vl / {vp, vs}, and ty 1, ty 2, ty 3 be the permutation of (t, vp, ui), (t, vs, ui), (t, vl, uj) such that ty h[Y ] = vh. The constraint CR ty 1,ty 2,ty 3 has only the variables in Y as active variables, and by arc consistency its relation must contain (t, vp, uj), (t, vs, uj), (t, vl, uj). By Observation 2, R must contain these tuples, a contradiction. 2. φt is bijective. Suppose that there exist i, j such that i = j and φt(vi) = uj. Let us / {uj, ui}, t = (t, vi, uj) and t = (t, φ 1 t (us), us). Let tx 1, tx 2, tx 3 be the permutation of the tuples ti, t , t such that tx h[x] = uh. Recall that ti is one of the three tuples associated with the constraint C = CR t1,t2,t3, and hence ti R , ti[Y ] = vi and ti[x] = ui. Then, the constraint CR tx 1,tx 2,tx 3 has x as the only active variable in its scope, and for every u D(x) its relation must contain the tuple tu such that tu[l] = ti[l] if l / Y {x}, tu[Y ] = φ 1(us), and tu[x] = u. Note that at this point, Observation 2 cannot be applied because ti may not belong to R(C). Let ta 1, ta 2, ta 3 be the permutation of ti, ts, t such that ta h[x] = uh. The constraint CR ta 1,ta 2,ta 3 has only ground variables in its scope except x, and its relation R must contain the tuple tf such that tf[x] = uj and tf[l] = t [l] otherwise. However, since R R we have tf R, a contradiction. Therefore, if φt is bijective then it must map every vi to ui. Now, suppose that there exists a partial tuple t such that φt is not equal to φt. By Case 1 and the reasoning above, φt must map every vi to the same value up. Let {vi, vj} = D(Y )\vp. If we denote by tb 1, tb 2, tb 3 the permutation of (t , vj, up), (t , vp, up) and (t, vi, ui) such that tb h[Y ] = vh, the constraint CR

tb 1,tb 2,tb 3 has only the variables in Y as active variables in its scope, and by arc consistency its relation must contain the tuple (t, vp, ui). By Observation 2, this tuple must belong to R, a contradiction. Finally, in this case every tuple must induce an indexequality between Y and x. Therefore, we can add x to the scope of Cy and continue the induction. 3. φt has range {u}. By Cases 1 and 2, we know that the only situation where the induction may not hold is when φt is in this case for every partial tuple t and every choice of Y . For each t R(C[S\x]) and

index-equality constrained set of variables Y , we define JY (t ) to be t plus the set of all tuples that differ from t only on the assignment to Y . By functionality, for each t R(C[S\x]) we can define ψ(t ) to be the sole value u D(x) such that (t , u) R. It is immediate that ψ(tα) = ψ(tβ) for each tα, tβ JY (t ), for any fixed Y , t . Furthermore, for any two tuples tα, tβ R(C[S\x]) such that tα[S|1,2(C)] = tβ[S|1,2(C)], there exists t Y1, . . . , t Yn such that t Y1 JY1(tα), tβ JYh(t Yn) and for each i, t Yi+1 JYi(t Yi). Unformally, starting from tα one can obtain tβ by changing the assignments to each Yi one by one. By transitivity of the equality, this means that ψ(tα) = ψ(tβ). Since this is true for any pair tα, tβ that share the same values for S|1,2(C), it follows that C[S|1,2(C) x] is functional in x, a contradiction with Lemma 3.

Theorem 1. There exists an algorithm that decides in polynomial time if a constraint language Γ admits a conservative Mal tsev polymorphism, and outputs one if one exists.

Proof. By Lemma 1, we can look for a conservative minority polymorphism instead. The algorithm builds IPcmin(Γ) in time O(rlt3), where l is the number of relations and t, r are respectively the maximum number of tuples and the maximum arity of a relation. IPcmin(Γ) has O(lt3 + d3) constraints and O(d3) variables. Then, we enforce GAC in time O(rlt4). By Proposition 1, assigning every variable xv1,v2,v3 with domain size 3 to v1 does not violate any constraint (since it respects index-equalities) and is consistent with every satisfying assignment to the remaining variables. Therefore, we can eliminate every variable with domain size 3. We are left with an instance whose active variables have domain size 2, and if it has a solution its language must have a conservative minority polymorphism (conservative polymorphisms are preserved by GAC). Note that all minority operations coincide on 2-elements domains; therefore, we can rename each domain by {0, 1} (arbitrarily) and obtain a CSP instance whose language has the unique Boolean minority polymorphism m(x, y, z) = x y + z mod 2. This instance is equivalent to a system of linear equations over GF(2), and any such instance with n variables and m constraints can be solved in time O(n2m) by Gaussian elimination. In our case, the running time is O(rlt3d6), and hence the complexity of the whole algorithm is O(rlt3d6 + rlt4).

If we interface our detection algorithm with the algorithm of (Dyer and Richerby 2013), we obtain the following corollary.

Corollary. The class of constraint languages with a conservative Mal tsev polymorphism is uniformly tractable.

5 Conservative majority constraints Unlike conservative Mal tsev polymorphisms, it is already known that conservative majority polymorphisms can be detected in polynomial time (Feder and Vardi 1998). The stateof-the-art algorithm, described in Section 2, has O(rd6lt4) time complexity (Bessiere et al. 2013). In the section, we will show that this algorithm can be greatly improved using the approach we described for conservative Mal tsev polymorphisms. As seen in Section 4, analyzing the structure of the indicator problem for languages of large arities can be tedious. Fortunately we need not do this twice, as languages with majority polymorphisms are 2-decomposable: each constraint can be replaced by its binary projections without altering the solution set of the instance (Jeavons, Cohen, and Cooper 1998). It is fairly straightforward to see that if a language Γ has a majority polymorphism, then the indicator problem of its 2-decomposition Γ2 is equivalent to the 2-decomposition of the indicator problem of Γ. We denote by IPcmaj(Γ2) the indicator problem of order 3 of Γ2 with the additional constraints xv1,v1,v2 {v1}, xv1,v2,v1 {v1}, xv2,v1,v1 {v1} for every v1, v2 D and xv1,v2,v3 {v1, v2, v3} for every v1, v2, v3 D. The solutions of IPcmaj(Γ2) are exactly the conservative majority polymorphisms of Γ2. Note that Observation 2 can be applied to IPcmaj(Γ2) since its proof only uses conservativity.

Lemma 4. If IPcmaj(Γ2) is GAC, the assignment

xu1,u2,u3 (ui D(xu1,u2,u3) | i is minimum)

is a solution.

Proof. We start by considering IPcmaj(Γ2) before GAC is applied. Let CR t1,t2,t3 = (S, R ) be a constraint of IPcmaj(Γ2) with scope (xu1,u2,u3, xv1,v2,v3) such that both variables are active (i.e. |{u1, u2, u3}| = 3 and |{v1, v2, v3}| = 3, as otherwise the unary majority constraints would force the variable to be ground). Suppose that there exists a pair i = j such that t = (ui, vj) R. Let k be the index such that k / {i, j} and (t 1, t 2, t 3) be the permutation of the tuples t, ti, tk such that t 1[2] = v1, t 2[2] = v2 and t 3[2] = v3. Consider the constraint CR t 1,t 2,t 3 = (S , R ). The second variable in S is xv1,v2,v3 and after arc-consistency the first variable will be fixed to the value ui. Therefore, by Observation 2, after arc-consistency the constraint CR t1,t2,t3 = (S, R) will contain the tuple (ui, v) for every v D(xv1,v2,v3). From this we can deduce that, after arc-consistency, for every i we have either (ui, vi) R or (ui, v) R for every v in the domain of xv1,v2,v3. In particular, if i and j are the minimum indices such that both ui and vi are in the domains, (ui, vj) always belongs to R.

Theorem 2. Conservative majority polymorphisms can be detected in time O(rlt4) in constraint languages with l distinct relations of arity at most r and containing at most t tuples.

Proof. The algorithm starts by assuming that a conservative majority polymorphism exists. We build IPcmaj(Γ) and enforce GAC in time O(rlt4). Since IPcmaj(Γ) is equivalent to IPcmaj(Γ2), we can use Lemma 4 to find a solution of the resulting instance. If this solution is a majority polymorphism of Γ (which can be verified in time O(rlt4)) the algorithm returns YES; otherwise it returns NO. The complexity of the whole procedure is O(rlt4).

This time bound improves on that of (Bessiere et al. 2013) by a factor of d6. Besides, the time complexity of our algorithm is roughly that of checking if a given conservative majority operation is a polymorphism of Γ, so there is little room for improvement.

6 Conclusion Using a detailed analysis of the indicator problem for conservative minority polymorphisms, we have designed a polynomial-time algorithm for detecting conservative Mal tsev polymorphisms in arbitrary constraint languages, and obtained as a side result a greatly improved algorithm for detecting conservative majority polymorphisms. As noted in the introduction, our results imply a uniform algorithm for constraint languages with a conservative Mal tsev polymorphism. Motivated by Observation 1, we make the following conjecture.

Conjecture 1. There exists a uniform algorithm for constraint languages with a Mal tsev polymorphism, and the meta-problem is decidable in polynomial-time.

The techniques we have developed in this paper make essential use of the fact that we are looking for conservative polymorphisms, and are unlikely to be sufficient to prove Conjecture 1 in its full generality. New ideas are needed, and it may be interesting to see if the algorithm from (Dyer and Richerby 2013) can be uniformized by using a different notion of compact representation of solution sets that only requires the promise that a Mal tsev polymorphism exists.

References Barto, L., and Kozik, M. 2014. Constraint satisfaction problems solvable by local consistency methods. J. ACM 61(1):3. Barto, L. 2011. The dichotomy for conservative constraint satisfaction problems revisited. In LICS, 301 310. IEEE Computer Society. Barto, L. 2015. The collapse of the bounded width hierarchy. Journal of Logic and Computation. Bessiere, C.; Carbonnel, C.; Hebrard, E.; Katsirelos, G.; and Walsh, T. 2013. Detecting and exploiting subproblem tractability. In Proceedings of the Twenty-Third international joint conference on Artificial Intelligence, 468 474. AAAI Press. Bulatov, A. A., and Dalmau, V. 2006. A simple algorithm for Mal tsev constraints. SIAM J. Comput. 36(1):16 27. Bulatov, A. A., and Marx, D. 2010. The complexity of global cardinality constraints. Logical Methods in Computer Science 6:1 27.

Bulatov, A. 2002. Mal tsev constraints are tractable. Technical report, Computing Laboratory, University of Oxford, Oxford, UK. Bulatov, A. 2003. Tractable conservative constraint satisfaction problems. In Proceedings 18th IEEE Symposium on Logic in Computer Science, LICS 03, 321 330. Bulatov, A. A. 2010. Bounded relational width. Technical report, School of Computer Science, Simon Fraser University. Carvalho, C.; Egri, L.; Jackson, M.; and Niven, T. 2011. On Maltsev digraphs. In Computer Science Theory and Applications. Springer. 181 194. Chen, H.; Dalmau, V.; and Grußien, B. 2013. Arc consistency and friends. J. Log. Comput. 23(1):87 108. Dyer, M., and Richerby, D. 2013. An effective dichotomy for the counting constraint satisfaction problem. SIAM Journal on Computing 42(3):1245 1274. Feder, T., and Vardi, M. Y. 1998. The computational structure of monotone monadic SNP and constraint satisfaction: A study through Datalog and group theory. SIAM Journal of Computing 28(1):57 104. Goldreich, O. 2010. P, NP, and NP-Completeness: The basics of computational complexity. Cambridge University Press. Green, M. J., and Cohen, D. A. 2008. Domain permutation reduction for constraint satisfaction problems. Artif. Intell. 172(8-9):1094 1118. Idziak, P. M.; Markovic, P.; Mc Kenzie, R.; Valeriote, M.; and Willard, R. 2007. Tractability and learnability arising from algebras with few subpowers. In LICS, 213 224. IEEE Computer Society. Jeavons, P. G.; Cohen, D. A.; and Cooper, M. C. 1998. Constraints, consistency and closure. Artif. Intell. 101(1 2):251 265. Jeavons, P.; Cohen, D. A.; and Gyssens, M. 1997. Closure properties of constraints. J. ACM 44(4):527 548. Kolaitis, P., and Vardi, M. 2000. Conjunctive-query containment and constraint satisfaction. Journal of Computer and System Sciences 61:302 332. Petke, J., and Jeavons, P. 2009. Tractable benchmarks for constraint programming. Technical report, Technical Report RR-09-07, Computing Laboratory, University of Oxford. Williams, R.; Gomes, C. P.; and Selman, B. 2003. Backdoors to typical case complexity. In Gottlob, G., and Walsh, T., eds., IJCAI, 1173 1178. Morgan Kaufmann.