2026-07-20T09:02:04Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8062 2024-03-06T10:40:49Z ddc:004 open_access

The Complexity of Boolean Surjective General-Valued CSPs Fulla, Peter Zivny, Stanislav constraint satisfaction problems surjective CSP valued CSP min-cut polymorphisms multimorphisms Valued constraint satisfaction problems (VCSPs) are discrete optimisation problems with the objective function given as a sum of fixed-arity functions; the values are rational numbers or infinity. In Boolean surjective VCSPs variables take on labels from D={0,1} and an optimal assignment is required to use both labels from D. A classic example is the global min-cut problem in graphs. Building on the work of Uppman, we establish a dichotomy theorem and thus give a complete complexity classification of Boolean surjective VCSPs. The newly discovered tractable case has an interesting structure related to projections of downsets and upsets. Our work generalises the dichotomy for {0,infinity}-valued constraint languages corresponding to CSPs) obtained by Creignou and Hebrard, and the dichotomy for {0,1}-valued constraint languages (corresponding to Min-CSPs) obtained by Uppman. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Peter Fulla and Stanislav Zivny 2017 Is Part Of LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2017.4 urn:nbn:de:0030-drops-80623 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.4 eng https://creativecommons.org/licenses/by/3.0/legalcode