The complexity of Boolean surjective general-valued CSPs
<p>Valued constraint satisfaction problems (VCSPs) are discrete optimisation problems with a $\overline{\mathbb{Q}}$-valued objective function given as a sum of fixed-arity functions, where $\overline{\mathbb{Q}}=\mathbb{Q}\cup\{\infty\}$ is the set of extended rationals.</p> <p>In...
| প্রধান লেখক: | , |
|---|---|
| বিন্যাস: | Journal article |
| প্রকাশিত: |
2017
|
| _version_ | 1826292367296036864 |
|---|---|
| author | Fulla, P Zivny, S |
| author_facet | Fulla, P Zivny, S |
| author_sort | Fulla, P |
| collection | OXFORD |
| description | <p>Valued constraint satisfaction problems (VCSPs) are discrete optimisation problems with a $\overline{\mathbb{Q}}$-valued objective function given as a sum of fixed-arity functions, where $\overline{\mathbb{Q}}=\mathbb{Q}\cup\{\infty\}$ is the set of extended rationals.</p> <p>In Boolean surjective VCSPs variables take on labels from $D=\{0,1\}$ and an optimal assignment is required to use both labels from $D$. A classic example is the global min-cut problem in graphs. Building on the work of Uppman, we establish a dichotomy theorem and thus give a complete complexity classification of Boolean surjective VCSPs. The newly discovered tractable case has an interesting structure related to projections of downsets and upsets. Our work generalises the dichotomy for $\{0,\infty\}$-valued constraint languages (corresponding to CSPs) obtained by Creignou and H\&apos;ebrard, and the dichotomy for $\{0,1\}$-valued constraint languages (corresponding to Min-CSPs) obtained by Uppman.</p> |
| first_indexed | 2024-03-07T03:13:35Z |
| format | Journal article |
| id | oxford-uuid:b50b5027-2c1f-4aea-999d-a5c23f59129f |
| institution | University of Oxford |
| last_indexed | 2024-03-07T03:13:35Z |
| publishDate | 2017 |
| record_format | dspace |
| spelling | oxford-uuid:b50b5027-2c1f-4aea-999d-a5c23f59129f2022-03-27T04:30:28ZThe complexity of Boolean surjective general-valued CSPsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:b50b5027-2c1f-4aea-999d-a5c23f59129fSymplectic Elements at Oxford2017Fulla, PZivny, S<p>Valued constraint satisfaction problems (VCSPs) are discrete optimisation problems with a $\overline{\mathbb{Q}}$-valued objective function given as a sum of fixed-arity functions, where $\overline{\mathbb{Q}}=\mathbb{Q}\cup\{\infty\}$ is the set of extended rationals.</p> <p>In Boolean surjective VCSPs variables take on labels from $D=\{0,1\}$ and an optimal assignment is required to use both labels from $D$. A classic example is the global min-cut problem in graphs. Building on the work of Uppman, we establish a dichotomy theorem and thus give a complete complexity classification of Boolean surjective VCSPs. The newly discovered tractable case has an interesting structure related to projections of downsets and upsets. Our work generalises the dichotomy for $\{0,\infty\}$-valued constraint languages (corresponding to CSPs) obtained by Creignou and H\&apos;ebrard, and the dichotomy for $\{0,1\}$-valued constraint languages (corresponding to Min-CSPs) obtained by Uppman.</p> |
| spellingShingle | Fulla, P Zivny, S The complexity of Boolean surjective general-valued CSPs |
| title | The complexity of Boolean surjective general-valued CSPs |
| title_full | The complexity of Boolean surjective general-valued CSPs |
| title_fullStr | The complexity of Boolean surjective general-valued CSPs |
| title_full_unstemmed | The complexity of Boolean surjective general-valued CSPs |
| title_short | The complexity of Boolean surjective general-valued CSPs |
| title_sort | complexity of boolean surjective general valued csps |
| work_keys_str_mv | AT fullap thecomplexityofbooleansurjectivegeneralvaluedcsps AT zivnys thecomplexityofbooleansurjectivegeneralvaluedcsps AT fullap complexityofbooleansurjectivegeneralvaluedcsps AT zivnys complexityofbooleansurjectivegeneralvaluedcsps |