# binarisation_via_dualisation_for_valued_constraints__79242843.pdf

Binarisation via Dualisation for Valued Constraints

David A. Cohen Royal Holloway University of London dave@cs.rhul.ac.uk

Martin C. Cooper IRIT University of Toulouse III cooper@irit.fr

Peter G. Jeavons, Stanislav ˇZivn y

University of Oxford {peter.jeavons,standa.zivny} @cs.ox.ac.uk

Constraint programming is a natural paradigm for many combinatorial optimisation problems. The complexity of constraint satisfaction for various forms of constraints has been widely-studied, both to inform the choice of appropriate algorithms, and to understand better the boundary between polynomial-time complexity and NP-hardness. In constraint programming it is well-known that any constraint satisfaction problem can be converted to an equivalent binary problem using the so-called dual encoding. Using this standard approach any ﬁxed collection of constraints, of arbitrary arity, can be converted to an equivalent set of constraints of arity at most two. Here we show that this transformation, although it changes the domain of the constraints, preserves all the relevant algebraic properties that determine the complexity. Moreover, we show that the dual encoding preserves many of the key algorithmic properties of the original instance. We also show that this remains true for more general valued constraint languages, where constraints may assign different cost values to different assignments. Hence, we obtain a simple proof of the fact that to classify the computational complexity of all valued constraint languages it sufﬁces to classify only binary valued constraint languages.

Introduction

There are two well-known methods for transforming a nonbinary constraint satisfaction problem (CSP) into a binary one; the dual encoding (Dechter and Pearl 1989) and the hidden variable encoding (Rossi, Dahr, and Petrie 1990). Both encode the non-binary constraints to variables that have as domains of possible values the valid tuples of the constraints. That is, the techniques derive a binary encoding of a non-binary constraint by changing the domain of the variables to an extensional representation of the original constraints. A combination of these two encodings, known as the double encoding, has also been studied (Smith, Stergiou, and Walsh 2000). It was observed in (Larrosa and Dechter

Stanislav ˇZivn y was supported by a Royal Society University Research Fellowship. Copyright c 2015, Association for the Advancement of Artiﬁcial Intelligence (www.aaai.org). All rights reserved.

2000) that both of these standard encodings can be extended to soft constraints. In this paper we focus on the dual encoding for the valued constraint satisfaction problem (VCSP). In particular, we consider the effect of this encoding on the set of weighted relations used to express the valued constraints. Different subproblems of the VCSP can be obtained by restricting, in various ways, the set of weighted relations that can be used to express the constraints. Such a set of weighted relations is generally called a valued constraint language (Cohen et al. 2013; Jeavons, Krokhin, and ˇZivn y 2014). For any such valued constraint language Γ there is a corresponding problem VCSP(Γ), and it has been shown that the computational complexity of VCSP(Γ) is determined by certain algebraic properties of the set Γ known as weighted polymorphisms (Cohen et al. 2013). Here we show that the dual encoding preserves many aspects of these algebraic properties. We show that there is a one-to-one correspondence between the weighted polymorphisms of the original valued constraint language and the weighted polymorphisms of the binary language obtained by the dual encoding. Hence, as well as providing a way to convert any given instance of the VCSP to an equivalent binary instance, the dual encoding also provides a way to convert any valued constraint language to a binary language with essentially the same algebraic properties, and hence essentially the same complexity and algorithmic properties.

Related work One special case of our results is the case when all the weighted relations in the valued constraint language we are considering are 0-weighted. This special case corresponds to the standard constraint satisfaction problem where constraints are speciﬁed by relations. In this special case, (Feder and Vardi 1998) and (Atserias 2008) showed that for any constraint language Γ there exists a constraint language Γ containing a single binary relation such that CSP(Γ) and CSP(Γ ) are polynomialtime equivalent. Recently, (Bul ın et al. 2013; 2014) have given a different construction that gives the same result but can be shown to preserve various types of identities involving the polymorphisms of Γ. Building on this approach, (Powell and Krokhin 2014) have shown that essentially the same construction as in (Bul ın et al. 2013; 2014) extends to the VCSP; in this case the valued constraint

Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence

language Γ contains a single unary weighted relation and a single binary relation. Our construction based on the standard dual encoding is considerably simpler. On the other hand, in our case the resulting Γ contains a single unary weighted relation, and more than one binary relation (in general). However, all the binary relations that we include in Γ are of the same type and correspond to enforcing equality on the shared variables between different constraints in instances of VCSP(Γ). Moreover, by allowing Γ to contain more than one binary relation we are able to preserve all identities involving polymorphisms of Γ, where an identity is an equality between arbitrary expressions involving only polymorphisms and all variables are universally quantiﬁed over the domain D. This is in contrast with the reduction (for the CSP) described in (Bul ın et al. 2013; 2014) and its extension (to the VCSP) described in (Powell and Krokhin 2014), which does not preserve the identities deﬁning Maltsev polymorphisms. In fact it is impossible for any reduction to a single binary relation to preserve such identities, without changing the algorithmic nature of the problem, because it has been shown that any single binary relation that has a Maltsev polymorphism also has a majority polymorphism (Kazda 2011). A similar transformation from constraint languages of arbitrary arity to sets of unary and binary relations was implicitly used in (Barto 2013), for the special case of the CSP. In a related but different direction, (Cohen, Jeavons, and ˇZivn y 2008) studied which valued constraint languages can be transformed to binary valued constraint languages over the same domain. It was shown in (ˇZivn y, Cohen, and Jeavons 2009) that there are submodular valued constraint languages which cannot be expressed (using min and sum) by binary submodular languages over the same domain.

The VCSP Throughout the paper, let D be a ﬁxed ﬁnite set and let Q = Q { } denote the set of rational numbers with inﬁnity. Deﬁnition 1. An m-ary weighted relation over D is any mapping φ : Dm Q. We denote by Φ(m) D the set of all m-ary weighted relations and let ΦD = S m 1 Φ(m) D .

We call D the domain, the elements of D labels (for variables), and we say that the weighted relations in ΦD take values (which are elements of Q). It is convenient to highlight the special case when the values taken by a weighted relation are restricted to 0 and . Deﬁnition 2. Any mapping φ : Dm {0, } will be called a 0-weighted relation (or simply a relation) and will often be identiﬁed with the set {x Dm | φ(x) = 0}. We denote by Feas(φ) = {x Dm | φ(x) < } the underlying feasibility relation of a given m-ary weighted relation. A weighted relation φ : Dm Q is called ﬁnitevalued if Feas(φ) = Dm. Deﬁnition 3. Let V = {x1, . . . , xn} be a set of variables. A valued constraint over V is an expression of the form φ(x) where φ Φ(m) D and x V m, for some positive integer m. The integer m is called the arity of the constraint, the

tuple x is called the scope of the constraint, and the weighted relation φ is called the constraint weighted relation. Deﬁnition 4. An instance of the valued constraint satisfaction problem (VCSP) is speciﬁed by a ﬁnite set V = {x1, . . . , xn} of variables, a ﬁnite set D of labels, and an objective function Φ expressed as follows:

Φ(x1, . . . , xn) =

i=1 φi(xi) (1)

where each φi(xi), 1 i q, is a valued constraint over V . Each constraint can appear multiple times in Φ. The goal is to ﬁnd an assignment of labels (a labelling) to the variables that minimises Φ. Deﬁnition 5. Any set Γ ΦD of weighted relations on some ﬁxed domain D is called a valued constraint language, or simply a language. We will denote by VCSP(Γ) the class of all VCSP instances in which the constraint weighted relations are all contained in Γ. The classical constraint satisfaction problem (CSP) (Dechter 2003) can be seen as a special case of the VCSP in which all weighted relations are in fact simply relations, (i.e., 0-weighted relations). A language containing only 0-weighted relations is called crisp. We will make use of the following simple but useful observation about arbitrary ﬁnite languages. Proposition 1. For any valued constraint language Γ such that |Γ| is ﬁnite, there is a valued constraint language Γ with |Γ | = 1, such that VCSP(Γ) and VCSP(Γ ) are polynomial-time equivalent.

Proof. Let Γ consist of q weighted relations, φ1, . . . , φq, with arities m1, . . . , mq, respectively. Without loss of generality, we assume that none of the φi are the constant function . Let m = Pq i=1 mi. Deﬁne the weighted relation φΓ, with arity m, by setting φΓ(x1, . . . , xm) = φ1(x1, . . . , xm1) + φ2(xm1+1, . . . , xm1+m2) + . . . + φq(xm mq+1, . . . , xm), and set Γ = {φΓ}. Any instance P of VCSP(Γ ) can clearly be expressed as an instance of VCSP(Γ). Conversely, for any instance P of VCSP(Γ) we can obtain an equivalent instance P of VCSP(Γ ) by simply adding irrelevant variables to the scope of each constraint φi(x), which are constrained by the elements of Γ \ {φi}, and then minimising over these. The assignments that minimise the objective function of P can then be obtained by taking the assignments that minimise the objective function of P and restricting them to the variables of P. Hence we have shown that VCSP(Γ) and VCSP(Γ ) are polynomial-time equivalent.

From a language Γ to a binary language Γd A language Γ is called binary if all weighted relations from Γ are of arity at most two. The goal of this paper is to study a certain type of transformation from an arbitrary ﬁnite language Γ to a binary language Γd such that VCSP(Γ) and VCSP(Γd) are polynomial-time equivalent. For any m-tuple x Dm we will write x[i] for its ith component.

Deﬁnition 6. Let Γ be any valued constraint language over D, and let φΓ be the corresponding weighted relation, of arity m, as deﬁned in the proof of Proposition 1. The dual of Γ, denoted Γd, is the binary valued constraint language with domain D = Feas(φΓ) Dm, deﬁned by

Γd = {φ Γ} [

i,j {1,...,m} {matchi,j} ,

where φ Γ : D Q is the unary weighted relation on D deﬁned by φ Γ(x) = φΓ(x1, x2, . . . , xm) for every x = (x1, x2, . . . , xm) D , and each matchi,j : D D Q is the binary 0-weighted relation on D deﬁned by

matchi,j(x, y) = 0 if x[i] = y[j], otherwise.

The language Γd contains a single unary weighted relation, which returns only ﬁnite values, together with k2 binary 0-weighted relations, and hence is a binary language. Example 1. Let Γ = {φeq}, where φeq is the equality relation on D, i.e., φeq : D D Q is deﬁned by φeq(x, y) = 0 if x = y and φeq(x, y) = if x = y. Then D = Feas(φeq) = {(a, a)|a D} and Γd consists of a single unary ﬁnite-valued relation φ , together with four binary 0-weighted relations match1,1, match1,2, match2,1, and match2,2. Moreover, φ (x) = 0 for every x D , and hence is trivial. All four of the other relations are in fact equal to the equality relation on D deﬁned by {((a, a), (a, a)) | (a, a) D }. Thus, the dual of the equality relation on D consists of a trivial unary relation, together with the equality relation on D , where |D| = |D |.

Example 2. Let Γ = {φsum}, where φsum : {0, 1}3 Q is deﬁned as follows:

φsum(x, y, z) = x + 2y + 3z if x + y + z = 1, otherwise.

Then D = Feas(φsum) = {(1, 0, 0), (0, 1, 0), (0, 0, 1)} and Γd consists of a single unary ﬁnite-valued relation φ sum, together with nine binary 0-weighted relations match1,1, match1,2, . . . , match3,3. If we set a = (1, 0, 0), b = (0, 1, 0), c = (0, 0, 1), then φ sum(a) = 1; φ sum(b) = 2 and φ sum(c) = 3. Also

match1,1(x, y) =

0 if (x, y) {(a, a), (b, b), (b, c), (c, b), (c, c)} otherwise

match1,2(x, y) =

0 if (x, y) {(a, b), (b, a), (b, a), (b, c), (c, a), (c, c)} otherwise

The dual encoding using Γd In this section we will describe the dual encoding described in (Dechter and Pearl 1989) for the CSP and later extended in (Larrosa and Dechter 2000) to soft constraint problems.

We will need the following notation. For any xi V m with xi = (xi1, . . . , xim), we write vars(xi) for the set {xi1, . . . , xim}. By Proposition 1, without loss of generality we shall assume that Γ contains a single weighted relation φΓ : Dm Q. Let P be an arbitrary instance of VCSP(Γ) with variables V = {x1, . . . , xn}, domain D, and constraints φΓ(x1), . . . , φΓ(xq), where xi V m for all 1 i q. We now describe the instance Pd in VCSP(Γd) which we call the dual of P.

The domain of Pd is D = Feas(φΓ) Dm. The variables V = {x 1, . . . , x q} of Pd correspond to the constraints of P. For every 1 i q, there is a unary constraint φ Γ(x i), where φ Γ : D Q is as deﬁned in Deﬁnition 6. If the scopes of two constraints of P, say φ(xi) and φ(xj), overlap, then there are binary constraints between x i and x j enforcing equality on the overlapping variables. More speciﬁcally, if xi = (xi1, . . . , xim), xj = (xj1, . . . , xjm), and vars(xi) vars(xj) = then there is a binary constraint matchk,l(x i, x j) for every k, l {1, . . . , m} with ik = jl.

The dual encoding provides a way to reduce instances of VCSP(Γ) to instances of VCSP(Γd). Our next result extends this observation to obtain the reverse reduction as well. Proposition 2. For any valued constraint language Γ such that |Γ| is ﬁnite, there is a binary valued constraint language Γd, such that VCSP(Γ) and VCSP(Γd) are polynomial-time equivalent.

Proof. By Proposition 1 we may assume that Γ consists of a single weighted relation φΓ : Dm Q. Moreover, since D is ﬁnite, and m is ﬁxed, we may assume that this weighted relation is given extensionally as a table of values. Hence, for any instance P of VCSP(Γ) we can construct in polynomial-time the dual instance Pd in VCSP(Γd) as deﬁned above. It is straightforward to show that the assignments that minimise the objective function of Pd correspond precisely to the assignments that minimise the objective function of P, and hence we have a polynomial-time reduction from VCSP(Γ) to VCSP(Γd). For the other direction, given any instance P in VCSP(Γd) we now indicate how to construct a corresponding instance P in VCSP(Γ). For each variable x i of P we introduce a fresh set of m variables for P. If there is a unary constraint φ Γ(x i) in P , then we introduce the constraint φΓ on the corresponding variables of P. If there is no unary constraint on x i, then we introduce the constraint Feas(φΓ) on the corresponding variables of P to code the fact that the domain of x i is D . If there is a binary constraint matchk,l(x i, x j) in P , then we merge the kth and lth variables in the corresponding sets of variables in P. This construction can be carried out in polynomial time. We have constructed an instance P in VCSP({φΓ, Feas(φΓ)}) such that assignments minimising the objective function of P correspond precisely

to assignments minimising the objective function of P . Hence we have established a polynomial time reduction from VCSP(Γd) to VCSP(Γ {Feas(φΓ)}). However, it follows from the proof of Theorem 4.3 of (Cohen et al. 2013) that VCSP(Γ {Feas(φΓ)}) can be reduced to VCSP(Γ) in polynomial-time.

Algebraic properties of Γd Over the past few years there has been considerable progress in investigating the complexity of different kinds of constraint satisfaction problems and valued constraint satisfaction problems by looking at the algebraic properties of the relations and weighted relations that deﬁne the constraints and valued constraints (Jeavons, Cohen, and Gyssens 1997; Jeavons 1998; Feder and Vardi 1998; Bulatov, Krokhin, and Jeavons 2005; Cohen et al. 2013)

Polymorphisms It was shown in (Jeavons, Cohen, and Gyssens 1997; Jeavons 1998) that the computational complexity of CSP(Γ), the class of CSP instances where the constraint relations all belong to some ﬁxed set Γ, is determined, up to polynomialtime reductions, by a set of operations known as the polymorphisms of Γ, which we will now deﬁne. We ﬁrst need some standard terminology. A function f : Dk D is called a k-ary operation on D. The kary projections, deﬁned for all 1 i k, are the operations e(k) i such that e(k) i (x1, . . . , xk) = xi. For any tuples x1, . . . , xk Dm, we denote by f(x1, . . . , xk) the tuple in Dm obtained by applying f to x1, . . . , xk componentwise.

Deﬁnition 7. Let φ : Dm Q be a weighted relation. An operation f : Dk D is a polymorphism of φ if, for any x1, . . . , xk Feas(φ) we have f(x1, . . . , xk) Feas(φ). We denote by Pol(Γ) the set of all operations on D which are polymorphisms of all φ Γ. We denote by Pol(k)(Γ) the k-ary operations in Pol(Γ).

It follows directly from the deﬁnition that all projections are polymorphisms of all valued constraint languages. Our next result shows that the polymorphisms of Γd are very closely related to the polymorphisms of Γ.

Theorem 1. Let Γ be a valued constraint language such that |Γ| is ﬁnite, and let Γd be the dual of Γ. The operation f Pol(k)(Γ) if and only if the operation fd Pol(k)(Γd) where fd(x1, . . . , xk) = f(x1, . . . , xk) for all xi in the domain of Γd.

Proof. By Proposition 1 we may assume that Γ consists of a single weighted relation φΓ : Dm Q, and hence that the domain D of Γd is a subset of Dm. First, consider any f : Dk D Pol(k)(Γ), and the corresponding fd : (D )k D given by fd(x1, . . . , xk) = f(x1, . . . , xk) for all xi Dm. Since f is a polymorphism of φΓ, it is also a polymorphism of the unary weighted relation φ Γ in Γd. It is straightforward to check that fd is also a polymorphism of all binary matchi,j relations in Γd (since it will return the same label at all positions where its arguments

have the same label). Hence fd Pol(k)(Γd). Now consider any fd : (D )k D Pol(k)(Γd). Since fd is a polymorphism of matchi,i it must return an element of D whose label in position i is a function, gi, of the labels in position i of its arguments. Moreover, since fd is a polymorphism of matchi,j, the functions gi and gj must return the same results for all possible arguments from D . Hence, there is a single function g : Dk D such that the result returned by fd(x1, . . . , xk) is equal to g(x1, . . . , xk). Now, since fd must return an element of D , it follows that g must be a polymorphism of φΓ, which gives the result.

The individual weighted relations in Γd often have other polymorphisms, that are not of the form indicated in Theorem 1, but the only polymorphisms that are shared by every weighted relation in Γd are those that correspond to polymorphisms of Γ in this way. Example 3. Recall the language Γ = {φsum}, deﬁned in Example 2. The weighted relation φsum has no polymorphisms, except for the projection operations on D = {0, 1}. However, the unary ﬁnite-valued relation φ sum, has every operation on D = {a, b, c} as a polymorphism. The binary 0-weighted relation match1,1 has many operations on D as polymorphisms, including all of the constant operations. The binary 0-weighted relation match1,2 also has many operations on D as polymorphisms, including the ternary majority operation g deﬁned by

g(x, y, z) =

x if x = y or x = z y if y = z c otherwise but not including the constant operation returning the label a, or the constant operation returning the label b. The only operations that are polymorphisms of every weighted relation in Γd are the projection operations on D . For certain types of languages Γ there are known to be polynomial-time algorithms to determine whether an instance of CSP(Γ) has an assignment that is allowed by all the constraints. In all known cases, these special-purpose algorithms can be applied precisely when Γ has polymorphisms that satisfy certain identities. For example, it is known (Feder and Vardi 1998; Jeavons, Cohen, and Cooper 1998) that enforcing 3-consistency can decide whether an instance has a solution if and only if Γ has a polymorphism g that satisﬁes the identities: g(x, x, y) = g(x, y, x) = g(y, x, x) = x x, y D. In fact, it is known that any crisp language that is not NPcomplete must have a polymorphism that satisﬁes certain kinds of identities (Bulatov, Krokhin, and Jeavons 2005). One simple consequence of Theorem 1 is that the polymorphisms of Γ and the polymorphisms of Γd satisfy exactly the same identities. Corollary 1. Let Γ be a valued constraint language such that |Γ| is ﬁnite, and let Γd be the dual of Γ. The operations in Pol(Γ) and the operations in Pol(Γd) satisfy exactly the same identities.

We will show below that it follows from Corollary 1 that essentially the same algorithms can be applied to either CSP(Γ) or CSP(Γd). Hence, from the point of view of the availability of known efﬁcient algorithms, it does not matter whether a CSP problem is formulated using constraints of arbitrary arity, or using a dual (binary) formulation. Although they satisfy the same identities, the polymorphisms of Γd do not, in general, share all the same properties as the polymorphisms of Γ. For example, Pol(Γ) might include the binary operation min that returns the smaller of its two arguments, according to some ﬁxed ordering of D. This operation has the property of being conservative, which means that the result is always equal to one of the arguments. However, the corresponding operation mind in Pol(Γd) is not generally conservative, since, for example, mind((a, b), (b, a)) = (a, a) for all a < b. One way to simplify the analysis of valued constraint languages is to restrict our attention to certain special kinds of languages that have desirable features. For example, a valued constraint language Γ is not a core if there is a label a D such that for any instance P VCSP(Γ) there is an optimal solution to P that does not use the label a. In this case, label a can be discarded.

Deﬁnition 8. A valued constraint language Γ is a core if all unary polymorphisms of Γ are bijections. Moreover, Γ is a rigid core if the only unary polymorphism of Γ is the identity function.

We can restrict our attention to languages that are rigid cores due to the following result.

Proposition 3 (Ochremiak 2014). For every valued constraint language Γ there is a valued constraint language Γ that is a rigid core and VCSP(Γ) and VCSP(Γ ) are polynomial-time equivalent.

An operation f : Dk D is called idempotent if f(x, . . . , x) = x for all x D. It is known that Γ is a rigid core if and only if all polymorphisms of Γ are idempotent (Ochremiak 2014).

Corollary 2. Let Γ be a valued constraint language such that |Γ| is ﬁnite, and let Γd be the dual of Γ. Γ is a rigid core if and only if Γd is a rigid core.

Proof. Follows immediately from Corollary 1, since the property of being idempotent is speciﬁed by an identity.

A precise characterisation of rigid core languages Γ that give rise to CSP instances solvable by any form of local consistency has recently been established (Barto and Kozik 2014). This characterisation makes use of the following identities for a k-ary (k 2) operation f:

f(y, x, . . . , x) = f(x, y, x, . . . , x) = f(x, . . . , x, y).

Any k-ary operation on D that satisﬁes these identities for all x, y D, is called a weak near-unanimity operation.

Theorem 2 (Barto and Kozik 2014). Let Γ be a crisp language that is a rigid core. CSP(Γ) is solvable by local consistency if and only if Pol(Γ) contains weak near-unanimity operations of all but ﬁnitely many arities.

A second polynomial-time algorithmic technique for the CSP generalises the idea of using Gaussian elimination to solve simultaneous linear equations. The most general version of this approach is based on the property of having a polynomial-sized representation for the solution set of any instance (Bulatov and Dalmau 2006; Idziak et al. 2010). Roughly, the algorithm works by starting from the empty set and adding constraints in an instance one by one while maintaining (in polynomial time) a small enough representation of the current solution set (of feasible assignments). At the end (i.e., after all constraints have been added), either this representation is non-empty and contains a solution to the instance or else there is no solution. This algorithm is called the few subpowers algorithm (because it is related to a certain algebraic property to do with the number of subalgebras in powers of an algebra). Languages where this algorithm is guaranteed to ﬁnd a solution (or show that none exists) were characterised by (Idziak et al. 2010). Once again, this characterisation involves a set of identities on the polymorphisms of the language. A k-ary (k 3) operation f : Dk D is called an edge operation if, for all x, y D,

f(y, y, x, x, . . . , x) = f(y, x, y, x, x, . . . , x) = x and

f(x, x, x, y, x, . . . , x) = f(x, x, x, x, y, x, . . . , x) = . . . = f(x, . . . , x, y) = x.

Theorem 3 (Idziak et al. 2010). Let Γ be a crisp language. Then CSP(Γ) is solvable by the few subpowers algorithm if Pol(Γ) contains an edge operation. The converse to this theorem is true in the following sense: the absence of edge operations from Pol(Γ) implies that the presence of small enough representations is not guaranteed, see (Idziak et al. 2010) for details. Combining Corollary 1 with Theorems 2 and 3 shows that the property of being solvable using local consistency, or the few subpowers algorithm, is possessed by a language Γ if and only if it is also possessed by the associated binary language Γd.

Weighted Polymorphisms Polymorphisms are sufﬁcient to analyse the complexity of the CSP, but for the VCSP, it has been shown that in general we need a more ﬂexible notion that assigns weights to a collection of polymorphisms (Cohen et al. 2013).

Deﬁnition 9. Let φ : Dm Q be a weighted relation, and let C Pol(k)(φ) be some collection of polymorphisms of φ. A function ω : C Q is called a k-ary weighted polymorphism of φ on C if it satisﬁes the following conditions: P f C ω(f) = 0; if ω(f) < 0, then f is a projection; for any x1, . . . , xk Feas(φ) X

f C ω(f)φ(f(x1, . . . , xk)) 0 . (2)

We denote by w Pol(k)(Γ) the set of all functions ω : Pol(k)(Γ) Q which are weighted polymorphisms of all φ Γ.

Example 4. Let D = {0, 1}. Let Γ be the set of weighted relations φ : Dm Q that admit ωsub as a weighted polymorphism, where ωsub is deﬁned by ωsub(f) = 1 if f {e(2) 1 , e(2) 2 }, ωsub(f) = +1 if f {min, max}, and ωsub(f) = 0 otherwise; here min and max are the binary operations returning the smaller and larger of their two arguments, respectively, wrt the usual order 0 < 1. In this case Γ is precisely the well-studied class of submodular set functions (Schrijver 2003). Our next result shows that the weighted polymorphisms of Γd are closely related to the weighted polymorphisms of Γ. Theorem 4. Let Γ be a valued constraint language such that |Γ| is ﬁnite, and let Γd be the dual of Γ. A function ω : Pol(k)(Γ) Q w Pol(k)(Γ) if and only if the function ωd : Pol(k)(Γd) Q w Pol(k)(Γd), where ωd(fd) = ω(f) for all f Pol(k)(Γ) and their corresponding operations fd Pol(k)(Γd) (as deﬁned in Theorem 1).

Proof. By Proposition 1 we may assume that Γ consists of a single weighted relation φΓ : Dm Q, and hence that the domain D of Γd is a subset of Dm. First, consider any ω : Pol(k)(Γ) Q w Pol(k)(Γ), and the corresponding ωd : Pol(k)(Γd) Q given by ωd(fd) = ω(f) for all f Pol(k)(Γ). Since ω is a weighted polymorphism of φΓ, it is easy to check that ωd satisﬁes all three conditions in Deﬁnition 9, and hence is a weighted polymorphism of the unary weighted relation φ Γ in Γd. Since all other weighted relations in Γd are the 0-weighted matchi,j relations, the third condition in Deﬁnition 9 holds trivially for all these weighted relations, and hence ωd is a weighted polymorphism of all weighted relations in Γd. Now consider any ωd : Pol(k)(Γd) Q w Pol(k)(Γd). Since ωd is a weighted polymorphism of φ Γ, the function ω : Pol(k)(Γ) Q that assigns the same weights to corresponding elements of Pol(k)(Γ) satisﬁes all the conditions of Deﬁnition 9, and hence is a weighted polymorphism of φΓ.

Weighted polymorphisms capture the complexity of any valued constraint language (Cohen et al. 2013). In fact, for any valued constraint language Γ, it was shown that the associated class of problems VCSP(Γ) is NP-hard, unless Γ has certain kinds of weighted polymorphisms. Moreover, the weighted polymorphisms of Γ can be used to select an appropriate algorithmic technique for VCSP(Γ). The algorithmic technique for the VCSP that has been most thoroughly investigated is based on linear programming: every VCSP instance Φ has a natural linear programming relaxation called the basic LP relaxation, and denoted BLP(Φ) - see (Kolmogorov, Thapper, and ˇZivn y 2013) and the references therein. Given a VCSP instance Φ, we say that BLP solves Φ if the solution to BLP(Φ) is equal to the minimal value of Φ over all assignments to the variables. Moreover, we say that BLP solves a valued constraint language Γ if BLP solves every instance Φ VCSP(Γ). It is shown in (Kolmogorov, Thapper, and ˇZivn y 2013) that in all cases where BLP solves Γ,

a standard self-reduction technique can be used to obtain an assignment that minimises any Φ in VCSP(Γ) in polynomial time. The power of BLP for valued constraint languages was fully characterised in (Thapper and ˇZivn y 2012). To state this result, we ﬁrst introduce some further terminology about operations. A k-ary operation f : Dk D is called symmetric if for every permutation π on {1, . . . , k}, it satisﬁes the identity

f(x1, . . . , xk) = f(xπ(1), . . . , xπ(k)).

A weighted polymorphism ω is called symmetric if it assigns positive weight to one or more symmetric operations, and no others. Theorem 5 (Thapper and ˇZivn y 2012). Let Γ be a valued constraint language. VCSP(Γ) can be solved using the BLP algorithm if and only if Γ has a k-ary symmetric weighted polymorphism, for every k 2. Example 5. A binary operation f : D2 D is called a semilattice operation if f is associative, commutative, and idempotent. Example of semilattice operations include the min and max operations on ordered sets that return the smaller or larger of their two arguments. Since any semilattice operation generates symmetric operations of all arities, Theorem 5 implies that any valued constraint language with a binary weighted polymorphism that assigns positive weight to some semilattice operation is solvable using the BLP. Such languages include the submodular languages (Example 4) and several others - see (Jeavons, Krokhin, and ˇZivn y 2014). Combining Corollary 1 with Theorem 4 and Theorem 5 shows that the property of being solvable using BLP is possessed by a language Γ if and only if it is also possessed by the associated binary language Γd.

Conclusion Transforming a constraint satisfaction problem to a binary problem has a number of advantages and disadvantages which have been investigated by many authors (Rossi, Dahr, and Petrie 1990; Bacchus et al. 2002; Stergiou and Samaras 2005). Such a transformation changes many aspects of the problem, such as what inferences can be derived by various kinds of propagation. One might expect that achieving the simplicity of a binary representation would incur a corresponding increase in the sophistication of the required solving algorithms. However, we have shown here that the well-known dual encoding of the VCSP converts any ﬁnite language, Γ, of arbitrary arity to a binary language, Γd, of a very restricted kind, such that there is a bijection between the polymorphisms of Γ and Γd, and the corresponding polymorphisms satisfy exactly the same identities and weightings. Hence we have shown that the algebraic analysis of valued constraint languages can focus on a very restricted class of binary languages. Moreover, many important algorithmic properties, such as the ability to solve problems using a bounded level of consistency, or by a linear programming relaxation, are also preserved by the dual encoding.

Atserias, A. 2008. On digraph coloring problems and treewidth duality. Eur. J. Comb. 29(4):796 820. Bacchus, F.; Chen, X.; van Beek, P.; and Walsh, T. 2002. Binary vs. non-binary constraints. Artiﬁcial Intelligence 140(1/2):1 37. Barto, L., and Kozik, M. 2014. Constraint Satisfaction Problems Solvable by Local Consistency Methods. Journal of the ACM 61(1). Article No. 3. Barto, L. 2013. Finitely related algebras in congruence distributive varieties have near unanimity terms. Canadian Journal of Mathematics 65:3 21. Bulatov, A., and Dalmau, V. 2006. A simple algorithm for Mal tsev constraints. SIAM Journal on Computing 36(1):16 27. Bulatov, A.; Krokhin, A.; and Jeavons, P. 2005. Classifying the Complexity of Constraints using Finite Algebras. SIAM Journal on Computing 34(3):720 742. Bul ın, J.; Delic, D.; Jackson, M.; and Niven, T. 2013. On the Reduction of the CSP Dichotomy Conjecture to Digraphs. In Proceedings of the 19th International Conference on Principles and Practice of Constraint Programming (CP 13), volume 8124 of Lecture Notes in Computer Science, 184 199. Springer. Bul ın, J.; Delic, D.; Jackson, M.; and Niven, T. 2014. A ﬁner reduction of constraint problems to digraphs. Technical report. ar Xiv:1406.6413. Cohen, D. A.; Cooper, M. C.; Creed, P.; Jeavons, P.; and ˇZivn y, S. 2013. An algebraic theory of complexity for discrete optimisation. SIAM Journal on Computing 42(5):915 1939. Cohen, D. A.; Jeavons, P. G.; and ˇZivn y, S. 2008. The expressive power of valued constraints: Hierarchies and collapses. Theoretical Computer Science 409(1):137 153. Dechter, R., and Pearl, J. 1989. Tree Clustering for Constraint Networks. Artiﬁcial Intelligence 38:353 366. Dechter, R. 2003. Constraint Processing. Morgan Kaufmann. 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 on Computing 28(1):57 104. Idziak, P. M.; Markovic, P.; Mc Kenzie, R.; Valeriote, M.; and Willard, R. 2010. Tractability and learnability arising from algebras with few subpowers. SIAM Journal on Computing 39(7):3023 3037. Jeavons, P.; Cohen, D.; and Cooper, M. C. 1998. Constraints, Consistency and Closure. Artiﬁcial Intelligence 101(1 2):251 265. Jeavons, P. G.; Cohen, D. A.; and Gyssens, M. 1997. Closure Properties of Constraints. Journal of the ACM 44(4):527 548. Jeavons, P.; Krokhin, A.; and ˇZivn y, S. 2014. The complexity of valued constraint satisfaction. Bulletin of the

European Association for Theoretical Computer Science (EATCS) 113:21 55. Jeavons, P. G. 1998. On the Algebraic Structure of Combinatorial Problems. Theoretical Computer Science 200(12):185 204. Kazda, A. 2011. Maltsev digraphs have a majority polymorphism. Eur. J. Comb. 32(3):390 397. Kolmogorov, V.; Thapper, J.; and ˇZivn y, S. 2013. The power of linear programming for general-valued CSPs. Technical report. ar Xiv:1311.4219. Submitted for publication. Larrosa, J., and Dechter, R. 2000. On the Dual Representation of non-Binary Semiring-based CSPs. In Workshop on Soft Constraints CP 00. Ochremiak, J. 2014. Algebraic properties of valued constraint satisfaction problem. Technical report. ar Xiv:1403.0476. Powell, R., and Krokhin, A. 2014. A reduction of VCSP to digraphs. Unpublished manuscript. Rossi, F.; Dahr, V.; and Petrie, C. 1990. On the Equivalence of Constraint Satisfaction Problems. In Proceedings of the 9th European Conference on Artiﬁcial Intelligence (ECAI 90). Schrijver, A. 2003. Combinatorial Optimization: Polyhedra and Efﬁciency, volume 24 of Algorithms and Combinatorics. Springer. Smith, B. M.; Stergiou, K.; and Walsh, T. 2000. Using auxiliary variables and implied constraints to model non-binary problems. In Proceedings of the 17th National Conference on Artiﬁcial Intelligence (AAAI 00), 182 187. Stergiou, K., and Samaras, N. 2005. Binary encodings of non-binary constraint satisfaction problems: Algorithms and experimental results. Journal of Artiﬁcial Intelligence Research (JAIR) 24:641 684. Thapper, J., and ˇZivn y, S. 2012. The power of linear programming for valued CSPs. In Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS 12), 669 678. IEEE. ˇZivn y, S.; Cohen, D. A.; and Jeavons, P. G. 2009. The Expressive Power of Binary Submodular Functions. Discrete Applied Mathematics 157(15):3347 3358.