An Algebraic Theory of Complexity for Valued Constraints: Establishing a Galois Connection

Abstract

The complexity of any optimisation problem depends critically on the form of the objective function. Valued constraint satisfaction problems are discrete optimisation problems where the function to be minimised is given as a sum of cost functions de ned on speci ed subsets of variables. These cost functions are chosen from some xed set ofavailable cost functions, known as a valued constraint language. We show in this paper that when the costs are non-negative rational numbers or in nite, then the complexity of a valued constraint problem is determined by certain algebraic properties of this valued constraint language, which we call weighted polymorphisms. We de ne a Galois connection between valued constraint languages and sets of weighted polymorphisms and show how the closed sets of this Galois connection can be characterised. These results provide a new approach in the search for tractable valued constraint languages.