OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

Binarisation for valued constraint satisfaction problems

Cohen, David A. and Cooper, Martin C. and Jeavons, Peter G. and Krokhin, Andrei and Powell, Robert and Zivny, Stanislav Binarisation for valued constraint satisfaction problems. (2017) SIAM Journal on Discrete Mathematics, 31 (4). 2279-2300. ISSN 0895-4801

(Document in English)

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

Official URL: http://dx.doi.org/10.1137/16M1088107


We study methods for transforming valued constraint satisfaction problems (VCSPs) to binary VCSPs. First, we show that the standard dual encoding preserves many aspects of the algebraic properties that capture the computational complexity of VCSPs. Second, we extend the reduction of CSPs to binary CSPs described by Bulén et al. [Log. Methods Comput. Sci., 11 (2015)] to VCSPs. This reduction establishes that VCSPs over a fixed valued constraint language are polynomial-time equivalent to minimum-cost homomorphism problems over a fixed digraph.

Item Type:Article
Additional Information:The original PDF is available at: http://epubs.siam.org/doi/10.1137/16M1088107
HAL Id:hal-01646073
Audience (journal):International peer-reviewed journal
Uncontrolled Keywords:
Institution:French research institutions > Centre National de la Recherche Scientifique - CNRS (FRANCE)
Other partners > Durham University (UNITED KINGDOM)
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:17 Nov 2017 14:30

Repository Staff Only: item control page