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 501kB |
Official URL: http://dx.doi.org/10.1137/16M1088107
Abstract
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: | |
Statistics: | download |
Deposited On: | 17 Nov 2017 14:30 |
Repository Staff Only: item control page