Conference icon

Conference

On planar valued CSPs

Abstract:

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...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed
Version:
Publisher's Version

Actions


Access Document


Files:
Publisher copy:
10.4230/LIPIcs.MFCS.2016.39

Authors


More by this author
Institution:
University of Oxford
Department:
Oxford, MPLS, Computer Science
More by this author
Institution:
University of Oxford
Department:
Oxford, MPLS, Computer Science
More from this funder
Funding agency for:
Zivny, S
Publisher:
Dagstuhl Publishing Publisher's website
Volume:
58
Pages:
1-14
Publication date:
2016
DOI:
ISSN:
1868-8969
URN:
uuid:46829ebf-a6a0-4be2-96dd-71c7b61a94c3
Source identifiers:
627173
Local pid:
pubs:627173
ISBN:
978-3-95977-016-3

Terms of use


Metrics



If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP