Skip to main content

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

David A. Cohen‚ Paidi Creed‚ Peter G. Jeavons and Stanislav Zivny

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.

Institution
OUCL
Month
November
Number
RR−10−16
Pages
30
Year
2010