Conference item
On planar valued CSPs
- Abstract:
- 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 Dvořák 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 Živný [JACM’13].
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Version of record, pdf, 510.1KB, Terms of use)
-
- Publisher copy:
- 10.4230/LIPIcs.MFCS.2016.39
Authors
- Publisher:
- Dagstuhl Publishing
- Host title:
- Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science
- Journal:
- MFCS 2016 More from this journal
- Volume:
- 58
- Pages:
- 1-14
- Publication date:
- 2016-01-01
- Acceptance date:
- 2016-06-05
- DOI:
- ISSN:
-
1868-8969
- ISBN:
- 9783959770163
- Keywords:
- Pubs id:
-
pubs:627173
- UUID:
-
uuid:46829ebf-a6a0-4be2-96dd-71c7b61a94c3
- Local pid:
-
pubs:627173
- Source identifiers:
-
627173
- Deposit date:
-
2016-06-10
- ARK identifier:
Terms of use
- Copyright holder:
- Fulla and Živný
- Copyright date:
- 2016
- Notes:
-
Copyright © Peter Fulla and Stanislav Živný;
licensed under Creative Commons License CC-BY
41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)
August 22-26, 2016, Krakow (Poland).
- Licence:
- CC Attribution (CC BY)
If you are the owner of this record, you can report an update to it here: Report update to this record