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.STACS.2019.52
URN: urn:nbn:de:0030-drops-102911
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10291/
Go to the corresponding LIPIcs Volume Portal

Matl, Gregor ; Zivný, Stanislav

Beyond Boolean Surjective VCSPs

pdf-format:
LIPIcs-STACS-2019-52.pdf (0.5 MB)

Abstract

Fulla, Uppman, and Zivný [ACM ToCT'18] established a dichotomy theorem for Boolean surjective general-valued constraint satisfaction problems (VCSPs), i.e., VCSPs on two-element domains in which both labels have to be used in a solution. This result, in addition to identifying the complexity frontier, features the discovery of a new non-trivial tractable case (called EDS) that does not appear in the non-surjective setting.
In this work, we go beyond Boolean domains. As our main result, we introduce a generalisation of EDS to arbitrary finite domains called SEDS (similar to EDS) and establish a conditional complexity classification of SEDS VCSPs based on a reduction to smaller domains. This gives a complete classification of SEDS VCSPs on three-element domains. The basis of our tractability result is a natural generalisation of the Min-Cut problem, in which only solutions of certain size (given by a lower and upper bound) are permitted. We show that all near-optimal solutions to this problem can be enumerated in polynomial time, which might be of independent interest.

BibTeX - Entry

@InProceedings{matl_et_al:LIPIcs:2019:10291,
  author =	{Gregor Matl and Stanislav Zivn{\'y}},
  title =	{{Beyond Boolean Surjective VCSPs}},
  booktitle =	{36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
  pages =	{52:1--52:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-100-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{126},
  editor =	{Rolf Niedermeier and Christophe Paul},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10291},
  doi =		{10.4230/LIPIcs.STACS.2019.52},
  annote =	{Keywords: constraint satisfaction problems, valued constraint satisfaction, surjective constraint satisfaction, graph cuts}
}

Keywords: constraint satisfaction problems, valued constraint satisfaction, surjective constraint satisfaction, graph cuts
Collection: 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
Issue Date: 2019
Date of publication: 12.03.2019

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