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....
| Príomhchruthaitheoirí: | , |
|---|---|
| Formáid: | Conference item |
| Foilsithe / Cruthaithe: |
Dagstuhl Publishing
2016
|
| _version_ | 1826270175967576064 |
|---|---|
| author | Fulla, P Zivny, S |
| author_facet | Fulla, P Zivny, S |
| author_sort | Fulla, P |
| collection | OXFORD |
| description | 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]. |
| first_indexed | 2024-03-06T21:36:44Z |
| format | Conference item |
| id | oxford-uuid:46829ebf-a6a0-4be2-96dd-71c7b61a94c3 |
| institution | University of Oxford |
| last_indexed | 2024-03-06T21:36:44Z |
| publishDate | 2016 |
| publisher | Dagstuhl Publishing |
| record_format | dspace |
| spelling | oxford-uuid:46829ebf-a6a0-4be2-96dd-71c7b61a94c32022-03-26T15:14:09ZOn planar valued CSPsConference itemhttp://purl.org/coar/resource_type/c_5794uuid:46829ebf-a6a0-4be2-96dd-71c7b61a94c3Symplectic Elements at OxfordDagstuhl Publishing2016Fulla, PZivny, SWe 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]. |
| spellingShingle | Fulla, P Zivny, S On planar valued CSPs |
| title | On planar valued CSPs |
| title_full | On planar valued CSPs |
| title_fullStr | On planar valued CSPs |
| title_full_unstemmed | On planar valued CSPs |
| title_short | On planar valued CSPs |
| title_sort | on planar valued csps |
| work_keys_str_mv | AT fullap onplanarvaluedcsps AT zivnys onplanarvaluedcsps |