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.2017.4
URN: urn:nbn:de:0030-drops-80623
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/8062/
Go to the corresponding LIPIcs Volume Portal

Fulla, Peter ; Zivny, Stanislav

The Complexity of Boolean Surjective General-Valued CSPs

pdf-format:
LIPIcs-MFCS-2017-4.pdf (0.5 MB)

Abstract

Valued constraint satisfaction problems (VCSPs) are discrete optimisation problems with the objective function given as a sum of fixed-arity functions; the values are rational numbers or infinity.

In Boolean surjective VCSPs variables take on labels from D={0,1} and an optimal assignment is required to use both labels from D. A classic example is the global min-cut problem in graphs. Building on the work of Uppman, we establish a dichotomy theorem and thus give a complete complexity classification of Boolean surjective VCSPs. The newly discovered tractable case has an interesting structure related to projections of downsets and upsets. Our work generalises the dichotomy for {0,infinity}-valued constraint languages corresponding to CSPs) obtained by Creignou and Hebrard, and the dichotomy for {0,1}-valued constraint languages (corresponding to Min-CSPs) obtained by Uppman.

BibTeX - Entry

@InProceedings{fulla_et_al:LIPIcs:2017:8062,
  author =	{Peter Fulla and Stanislav Zivny},
  title =	{{The Complexity of Boolean Surjective General-Valued CSPs}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{4:1--4:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Kim G. Larsen and Hans L. Bodlaender and Jean-Francois Raskin},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/8062},
  URN =		{urn:nbn:de:0030-drops-80623},
  doi =		{10.4230/LIPIcs.MFCS.2017.4},
  annote =	{Keywords: constraint satisfaction problems, surjective CSP, valued CSP, min-cut, polymorphisms, multimorphisms}
}

Keywords: constraint satisfaction problems, surjective CSP, valued CSP, min-cut, polymorphisms, multimorphisms
Collection: 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)
Issue Date: 2017
Date of publication: 01.12.2017

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