2026-08-16T23:13:56Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6453 2024-03-06T10:38:18Z ddc:004 open_access

On Planar Valued CSPs Fulla, Peter Zivny, Stanislav constraint satisfaction valued constraint satisfaction planarity polymorphisms multimorphisms We study the computational complexity of planar valued constraint satisfaction problems (VCSPs). First, we show that intractable Boolean VCSPs have to be self-complementary to be tractable in the planar setting, thus extending a corresponding result of Dvorak and Kupec [ICALP'15] from CSPs to VCSPs. Second, we give a complete complexity classification of conservative planar VCSPs on arbitrary finite domains. As it turns out, in this case planarity does not lead to any new tractable cases, and thus our classification is a sharpening of the classification of conservative VCSPs by Kolmogorov and Zivny [JACM'13]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Peter Fulla and Stanislav Zivny 2016 Is Part Of LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2016.39 urn:nbn:de:0030-drops-64537 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.39 eng https://creativecommons.org/licenses/by/3.0/legalcode