Using a min-cut generalisation to go beyond Boolean surjective VCSPs
In this work, we first study a natural generalisation of the Min-Cut problem, where a graph is augmented by a superadditive set function defined on its vertex subsets. The goal is to select a vertex subset such that the weight of the induced cut plus the set function value are minimised. In addition...
| Main Authors: | , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Springer
2020
|
| _version_ | 1797076449736261632 |
|---|---|
| author | Matl, G Zivny, S |
| author_facet | Matl, G Zivny, S |
| author_sort | Matl, G |
| collection | OXFORD |
| description | In this work, we first study a natural generalisation of the Min-Cut problem, where a graph is augmented by a superadditive set function defined on its vertex subsets. The goal is to select a vertex subset such that the weight of the induced cut plus the set function value are minimised. In addition, a lower and upper bound is imposed on the solution size. We present a polynomial-time algorithm for enumerating all near-optimal solutions of this Bounded Generalised Min-Cut problem. Second, we apply this novel algorithm to surjective general-valued constraint satisfaction problems (VCSPs), i.e., VCSPs in which each label has to be used at least once. On the Boolean domain, Fulla, Uppman, and Živný (ACM ToCT’18) have recently established a complete classification of surjective VCSPs based on an unbounded version of the Generalised Min-Cut problem. Their result features the discovery of a new non-trivial tractable case called EDS that does not appear in the non-surjective setting. As our main result, we extend the class EDS to arbitrary finite domains and provide a conditional complexity classification for surjective VCSPs of this type based on a reduction to smaller domains. On three-element domains, this leads to a complete classification of such VCSPs. |
| first_indexed | 2024-03-07T00:03:57Z |
| format | Journal article |
| id | oxford-uuid:76e97cd3-b4dd-4bbd-a185-35d21cd4c438 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T00:03:57Z |
| publishDate | 2020 |
| publisher | Springer |
| record_format | dspace |
| spelling | oxford-uuid:76e97cd3-b4dd-4bbd-a185-35d21cd4c4382022-03-26T20:19:32ZUsing a min-cut generalisation to go beyond Boolean surjective VCSPsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:76e97cd3-b4dd-4bbd-a185-35d21cd4c438EnglishSymplectic ElementsSpringer2020Matl, GZivny, SIn this work, we first study a natural generalisation of the Min-Cut problem, where a graph is augmented by a superadditive set function defined on its vertex subsets. The goal is to select a vertex subset such that the weight of the induced cut plus the set function value are minimised. In addition, a lower and upper bound is imposed on the solution size. We present a polynomial-time algorithm for enumerating all near-optimal solutions of this Bounded Generalised Min-Cut problem. Second, we apply this novel algorithm to surjective general-valued constraint satisfaction problems (VCSPs), i.e., VCSPs in which each label has to be used at least once. On the Boolean domain, Fulla, Uppman, and Živný (ACM ToCT’18) have recently established a complete classification of surjective VCSPs based on an unbounded version of the Generalised Min-Cut problem. Their result features the discovery of a new non-trivial tractable case called EDS that does not appear in the non-surjective setting. As our main result, we extend the class EDS to arbitrary finite domains and provide a conditional complexity classification for surjective VCSPs of this type based on a reduction to smaller domains. On three-element domains, this leads to a complete classification of such VCSPs. |
| spellingShingle | Matl, G Zivny, S Using a min-cut generalisation to go beyond Boolean surjective VCSPs |
| title | Using a min-cut generalisation to go beyond Boolean surjective VCSPs |
| title_full | Using a min-cut generalisation to go beyond Boolean surjective VCSPs |
| title_fullStr | Using a min-cut generalisation to go beyond Boolean surjective VCSPs |
| title_full_unstemmed | Using a min-cut generalisation to go beyond Boolean surjective VCSPs |
| title_short | Using a min-cut generalisation to go beyond Boolean surjective VCSPs |
| title_sort | using a min cut generalisation to go beyond boolean surjective vcsps |
| work_keys_str_mv | AT matlg usingamincutgeneralisationtogobeyondbooleansurjectivevcsps AT zivnys usingamincutgeneralisationtogobeyondbooleansurjectivevcsps |