Binarisation via Dualisation for Valued Constraints

David Cohen, Martin Cooper, Peter Jeavons, Stanislav Živný

Research output: Contribution to conferencePaperpeer-review

47 Downloads (Pure)

Abstract

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 fixed 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 suffices to classify only binary valued constraint languages.
Original languageEnglish
Pages3731-3737
Number of pages7
Publication statusPublished - Jan 2015
EventTwenty-Ninth AAAI Conference on Artificial Intelligence - Hyatt Regency, Austin, Austin, United States
Duration: 25 Jan 201529 Jan 2015

Conference

ConferenceTwenty-Ninth AAAI Conference on Artificial Intelligence
Country/TerritoryUnited States
CityAustin
Period25/01/1529/01/15

Cite this