DROPS

Document

DOI: 10.4230/LIPIcs.CSL.2017.42

An Algebraic Approach to Valued Constraint Satisfaction

Authors: Rostislav Horcík, Tommaso Moraschini, and Amanda Vidal

Published in: LIPIcs, Volume 82, 26th EACSL Annual Conference on Computer Science Logic (CSL 2017)

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.

Cite as

Rostislav Horcík, Tommaso Moraschini, and Amanda Vidal. An Algebraic Approach to Valued Constraint Satisfaction. In 26th EACSL Annual Conference on Computer Science Logic (CSL 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 82, pp. 42:1-42:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{horcik_et_al:LIPIcs.CSL.2017.42,
  author =	{Horc{\'\i}k, Rostislav and Moraschini, Tommaso and Vidal, Amanda},
  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 =	{Goranko, Valentin and Dam, Mads},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2017.42},
  URN =		{urn:nbn:de:0030-drops-76767},
  doi =		{10.4230/LIPIcs.CSL.2017.42},
  annote =	{Keywords: Valued CSP, Polymorphism, pp-definability, Geiger’s Theorem.}
}

Search Results

Documents authored by Vidal, Amanda

An Algebraic Approach to Valued Constraint Satisfaction

Abstract

Cite as

Thanks for your feedback!

Could not send message