Beyond boolean surjective VCSPs
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 frontie...
| Main Authors: | , |
|---|---|
| Format: | Conference item |
| Published: |
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
2019
|
| _version_ | 1797100027169996800 |
|---|---|
| author | Matl, G Zivny, S |
| author_facet | Matl, G Zivny, S |
| author_sort | Matl, G |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-07T05:31:55Z |
| format | Conference item |
| id | oxford-uuid:e28ed1aa-2ade-46e3-8e67-181c205c2689 |
| institution | University of Oxford |
| last_indexed | 2024-03-07T05:31:55Z |
| publishDate | 2019 |
| publisher | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |
| record_format | dspace |
| spelling | oxford-uuid:e28ed1aa-2ade-46e3-8e67-181c205c26892022-03-27T10:02:15ZBeyond boolean surjective VCSPsConference itemhttp://purl.org/coar/resource_type/c_5794uuid:e28ed1aa-2ade-46e3-8e67-181c205c2689Symplectic Elements at OxfordSchloss Dagstuhl - Leibniz-Zentrum für Informatik2019Matl, GZivny, SFulla, 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. |
| spellingShingle | Matl, G Zivny, S Beyond boolean surjective VCSPs |
| title | Beyond boolean surjective VCSPs |
| title_full | Beyond boolean surjective VCSPs |
| title_fullStr | Beyond boolean surjective VCSPs |
| title_full_unstemmed | Beyond boolean surjective VCSPs |
| title_short | Beyond boolean surjective VCSPs |
| title_sort | beyond boolean surjective vcsps |
| work_keys_str_mv | AT matlg beyondbooleansurjectivevcsps AT zivnys beyondbooleansurjectivevcsps |