On Planar Valued CSPs
arXiv:1602.06323 · doi:10.1016/j.jcss.2017.03.005
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].
A full version of an MFCS'16 paper. Improved presentation compared to v1 and v2
References in corpus (6)
- The power of linear programming for general-valued CSPs
- The power of Sherali-Adams relaxations for general-valued CSPs
- Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP
- Necessary conditions for tractability of valued CSPs
- A Galois Connection for Weighted (Relational) Clones of Infinite Size
- Hybrid VCSPs with crisp and conservative valued templates