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.CSL.2017.42
URN: urn:nbn:de:0030-drops-76767
URL: http://dagstuhl.sunsite.rwth-aachen.de/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.
Collection: 26th EACSL Annual Conference on Computer Science Logic (CSL 2017)
Issue Date: 2017
Date of publication: 16.08.2017

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