License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CSL.2017.42
URN: urn:nbn:de:0030-drops-76767
URL: http://drops.dagstuhl.de/opus/volltexte/2017/7676/
Go to the corresponding LIPIcs Volume Portal


HorcŪk, Rostislav ; Moraschini, Tommaso ; Vidal, Amanda

An Algebraic Approach to Valued Constraint Satisfaction

pdf-format:
LIPIcs-CSL-2017-42.pdf (0.6 MB)


Abstract

We study the complexity of the valued CSP (VCSP, for short) over arbitrary templates, taking the general framework of integral bounded linearly order monoids as valuation structures. The class of problems considered here subsumes and generalizes the most common one in VCSP literature, since both monoidal and lattice conjunction operations are allowed in the formulation of constraints. Restricting to locally finite monoids, we introduce a notion of polymorphism that captures the pp-definability in the style of Geigerís result. As a consequence, sufficient conditions for tractability of the classical CSP, related to the existence of certain polymorphisms, are shown to serve also for the valued case. Finally, we establish the dichotomy conjecture for the VCSP, modulo the dichotomy for classical CSP.

BibTeX - Entry

@InProceedings{horck_et_al:LIPIcs:2017:7676,
  author =	{Rostislav Horc{\'i}k and Tommaso Moraschini and Amanda Vidal},
  title =	{{An Algebraic Approach to Valued Constraint Satisfaction}},
  booktitle =	{26th EACSL Annual Conference on Computer Science Logic (CSL 2017)},
  pages =	{42:1--42:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-045-3},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{82},
  editor =	{Valentin Goranko and Mads Dam},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7676},
  URN =		{urn:nbn:de:0030-drops-76767},
  doi =		{10.4230/LIPIcs.CSL.2017.42},
  annote =	{Keywords: Valued CSP, Polymorphism, pp-definability, Geigerís Theorem.}
}

Keywords: Valued CSP, Polymorphism, pp-definability, Geigerís Theorem.
Seminar: 26th EACSL Annual Conference on Computer Science Logic (CSL 2017)
Issue Date: 2017
Date of publication: 14.08.2017


DROPS-Home | Fulltext Search | Imprint Published by LZI