Point-width and Max-CSPs
<p>The complexity of (unbounded-arity) Max-CSPs under structural restrictions is poorly understood. The two most general hypergraph properties known to ensure tractability of Max-CSPs, β-acyclicity and bounded (incidence) MIM-width, are incomparable and lead to very different algorithms.</p...
| Main Authors: | , , |
|---|---|
| 格式: | Journal article |
| 语言: | English |
| 出版: |
Association for Computing Machinery
2020
|
| _version_ | 1826294735185117184 |
|---|---|
| author | Carbonnel, C Romero, M Živný, S |
| author_facet | Carbonnel, C Romero, M Živný, S |
| author_sort | Carbonnel, C |
| collection | OXFORD |
| description | <p>The complexity of (unbounded-arity) Max-CSPs under structural restrictions is poorly understood. The two most general hypergraph properties known to ensure tractability of Max-CSPs, β-acyclicity and bounded (incidence) MIM-width, are incomparable and lead to very different algorithms.</p>
<p>We introduce the framework of point decompositions for hypergraphs and use it to derive a new sufficient condition for the tractability of (structurally restricted) Max-CSPs, which generalises both bounded MIM-width and β-acyclicity. On the way, we give a new characterisation of bounded MIM-width and discuss other hypergraph properties which are relevant to the complexity of Max-CSPs, such as β-hypertreewidth.</p> |
| first_indexed | 2024-03-07T03:50:15Z |
| format | Journal article |
| id | oxford-uuid:c0ff3bd7-b7f8-4cd8-8d2e-cdfb96f2b2f5 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T03:50:15Z |
| publishDate | 2020 |
| publisher | Association for Computing Machinery |
| record_format | dspace |
| spelling | oxford-uuid:c0ff3bd7-b7f8-4cd8-8d2e-cdfb96f2b2f52022-03-27T05:58:24ZPoint-width and Max-CSPsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:c0ff3bd7-b7f8-4cd8-8d2e-cdfb96f2b2f5EnglishSymplectic ElementsAssociation for Computing Machinery2020Carbonnel, CRomero, MŽivný, S<p>The complexity of (unbounded-arity) Max-CSPs under structural restrictions is poorly understood. The two most general hypergraph properties known to ensure tractability of Max-CSPs, β-acyclicity and bounded (incidence) MIM-width, are incomparable and lead to very different algorithms.</p> <p>We introduce the framework of point decompositions for hypergraphs and use it to derive a new sufficient condition for the tractability of (structurally restricted) Max-CSPs, which generalises both bounded MIM-width and β-acyclicity. On the way, we give a new characterisation of bounded MIM-width and discuss other hypergraph properties which are relevant to the complexity of Max-CSPs, such as β-hypertreewidth.</p> |
| spellingShingle | Carbonnel, C Romero, M Živný, S Point-width and Max-CSPs |
| title | Point-width and Max-CSPs |
| title_full | Point-width and Max-CSPs |
| title_fullStr | Point-width and Max-CSPs |
| title_full_unstemmed | Point-width and Max-CSPs |
| title_short | Point-width and Max-CSPs |
| title_sort | point width and max csps |
| work_keys_str_mv | AT carbonnelc pointwidthandmaxcsps AT romerom pointwidthandmaxcsps AT zivnys pointwidthandmaxcsps |