OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

Binarisation via Dualisation for Valued Constraints

Cohen, David A. and Cooper, Martin C. and Jeavons, Peter G. and Zivny, Stanislav Binarisation via Dualisation for Valued Constraints. (2015) In: 29th AAAI Conference on Artificial Intelligence (AAAI 2015), 25 January 2015 - 30 January 2015 (Austin, Texas, United States).

(Document in English)

PDF (Author's version) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader

Official URL: http://www.aaai.org/ocs/index.php/AAAI/AAAI15/paper/view/9328


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.

Item Type:Conference or Workshop Item (Paper)
Additional Information:Thanks to ACM editor. The definitive version is available at http://dl.acm.org This papers appears in Proceedings of AAAI'15 ISBN:0-262-51129-0 ISSN 2159-5399 The original PDF is available at: http://dl.acm.org/citation.cfm?id=2888116.2888234
HAL Id:hal-04079582
Audience (conference):International conference proceedings
Uncontrolled Keywords:
Institution:French research institutions > Centre National de la Recherche Scientifique - CNRS (FRANCE)
Université de Toulouse > Institut National Polytechnique de Toulouse - Toulouse INP (FRANCE)
Université de Toulouse > Université Toulouse III - Paul Sabatier - UT3 (FRANCE)
Université de Toulouse > Université Toulouse - Jean Jaurès - UT2J (FRANCE)
Université de Toulouse > Université Toulouse 1 Capitole - UT1 (FRANCE)
Other partners > University of London (UNITED KINGDOM)
Other partners > University of Oxford (UNITED KINGDOM)
Laboratory name:
Deposited On:10 Oct 2016 09:42

Repository Staff Only: item control page