On planar valued CSPs
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....
| Những tác giả chính: | , |
|---|---|
| Định dạng: | Conference item |
| Được phát hành: |
Dagstuhl Publishing
2016
|
| Tóm tắt: | 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]. |
|---|