On planar valued CSPs
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 correspond...
| Main Authors: | , |
|---|---|
| Format: | Journal article |
| Published: |
Elsevier
2017
|
| _version_ | 1797090122852728832 |
|---|---|
| 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), 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]. |
| first_indexed | 2024-03-07T03:13:58Z |
| format | Journal article |
| id | oxford-uuid:b528c827-0e5c-47e7-be6b-b195db21550f |
| institution | University of Oxford |
| last_indexed | 2024-03-07T03:13:58Z |
| publishDate | 2017 |
| publisher | Elsevier |
| record_format | dspace |
| spelling | oxford-uuid:b528c827-0e5c-47e7-be6b-b195db21550f2022-03-27T04:31:24ZOn planar valued CSPsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:b528c827-0e5c-47e7-be6b-b195db21550fSymplectic Elements at OxfordElsevier2017Fulla, PZivny, SWe 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]. |
| 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 |