On planar valued CSPs

descriptionPublicationkeyboard_double_arrow_right Article , Preprint , Conference object 01 Aug 2017Embargo end date: 01 Jan 2016 Germany, United Kingdom English Publisher:Elsevier BVJournal:Journal of Computer and System Sciences, volume 87, pages 104-118 (issn: 0022-0000,

Copyright policy )Funded by:EC | PowAlgDO

Authors: Fulla, Peter; Živný, Stanislav;

doi: 10.1016/j.jcss.2017.03.005 , 10.48550/arxiv.1602.06323

arXiv: 1602.06323

On planar valued CSPs

- Summary
- Subjects
- Metrics

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

Countries

Germany, United Kingdom

Related Organizations

University of Oxford
United Kingdom
Leibniz Association
Germany
THE CHANCELLOR, MASTERS AND SCHOLARS OF THE UNIVERSITY OF OXFORD
United Kingdom
Schloss Dagstuhl – Leibniz Center for Informatics
Germany

Keywords

FOS: Computer and information sciences, multimorphisms, Discrete Mathematics (cs.DM), Analysis of algorithms and problem complexity, constraint satisfaction, valued constraint satisfaction, planarity, Computational Complexity (cs.CC), 004, Computer Science - Computational Complexity, Graph theory (including graph drawing) in computer science, F.2.2, polymorphisms, Computer Science - Discrete Mathematics, ddc: ddc:004

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	0
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Average
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average