License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2016.39
URN: urn:nbn:de:0030-drops-64537
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6453/
Go to the corresponding LIPIcs Volume Portal

Fulla, Peter ; Zivny, Stanislav

On Planar Valued CSPs

pdf-format:
LIPIcs-MFCS-2016-39.pdf (0.5 MB)

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 Dvorak 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 Zivny [JACM'13].

BibTeX - Entry

@InProceedings{fulla_et_al:LIPIcs:2016:6453,
  author =	{Peter Fulla and Stanislav Zivny},
  title =	{{On Planar Valued CSPs}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{39:1--39:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Piotr Faliszewski and Anca Muscholl and Rolf Niedermeier},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6453},
  URN =		{urn:nbn:de:0030-drops-64537},
  doi =		{10.4230/LIPIcs.MFCS.2016.39},
  annote =	{Keywords: constraint satisfaction, valued constraint satisfaction, planarity, polymorphisms, multimorphisms}
}

Keywords: constraint satisfaction, valued constraint satisfaction, planarity, polymorphisms, multimorphisms
Collection: 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)
Issue Date: 2016
Date of publication: 19.08.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI