Journal article
On planar valued CSPs
- Abstract:
- We study the computational complexity of planar valued constraint satisfaction problems (VCSPs), which require the incidence graph of the instance be planar. 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. 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].
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Accepted manuscript, pdf, 386.5KB, Terms of use)
-
- Publisher copy:
- 10.1016/j.jcss.2017.03.005
Authors
- Publisher:
- Elsevier
- Journal:
- Journal of Computer and System Sciences More from this journal
- Volume:
- 87
- Pages:
- 104-118
- Publication date:
- 2017-03-18
- Acceptance date:
- 2017-03-11
- DOI:
- EISSN:
-
1090-2724
- ISSN:
-
0022-0000
- Pubs id:
-
pubs:685326
- UUID:
-
uuid:b528c827-0e5c-47e7-be6b-b195db21550f
- Local pid:
-
pubs:685326
- Source identifiers:
-
685326
- Deposit date:
-
2017-03-11
- ARK identifier:
Terms of use
- Copyright holder:
- © 2017 Elsevier Inc All rights reserved
- Copyright date:
- 2017
- Notes:
- This is the author accepted manuscript following peer review version of the article. The final version is available online from Elsevier at: 10.1016/j.jcss.2017.03.005
If you are the owner of this record, you can report an update to it here: Report update to this record