Beyond boolean surjective VCSPs

Conference item

Fulla, Uppman, and Živný [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.

Authors: Matl, G; Zivny, S

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
• Host title: 36th International Symposium on Theoretical Aspects of Computer Science
• Journal: 36th International Symposium on Theoretical Aspects of Computer Science
• Volume: 48
• Pages: 48:1–48:15
• Publication date: 2019-03-12
• Acceptance date: 2018-12-20
• Event location: Berlin, Germany
• DOI: 10.4230/LIPIcs.STACS.2019.48
• EISSN: 1868-8969
• Keywords: constraint satisfaction problems; surjective constraint satisfaction; graph cuts; valued constraint satisfaction