Pliability and approximating max-CSPs
We identify a sufficient condition, treewidth-pliability, that gives a polynomial-time algorithm for an arbitrarily good approximation of the optimal value in a large class of Max-2-CSPs parameterised by the class of allowed constraint graphs (with arbitrary constraints on an unbounded alphabet). Ou...
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Association for Computing Machinery
2023
|
| _version_ | 1797111549255483392 |
|---|---|
| author | Romero, M Wrochna, M Zivny, S |
| author_facet | Romero, M Wrochna, M Zivny, S |
| author_sort | Romero, M |
| collection | OXFORD |
| description | We identify a sufficient condition, treewidth-pliability, that gives a polynomial-time
algorithm for an arbitrarily good approximation of the optimal value in a large class of
Max-2-CSPs parameterised by the class of allowed constraint graphs (with arbitrary constraints on an unbounded alphabet). Our result applies more generally to the maximum
homomorphism problem between two rational-valued structures.
The condition unifies the two main approaches for designing a polynomial-time approximation scheme. One is Baker’s layering technique, which applies to sparse graphs
such as planar or excluded-minor graphs. The other is based on Szemer´edi’s regularity
lemma and applies to dense graphs. We extend the applicability of both techniques to
new classes of Max-CSPs. On the other hand, we prove that the condition cannot be used
to find solutions (as opposed to approximating the optimal value) in general.
Treewidth-pliability turns out to be a robust notion that can be defined in several
equivalent ways, including characterisations via size, treedepth, or the Hadwiger number.
We show connections to the notions of fractional-treewidth-fragility from structural graph
theory, hyperfiniteness from the area of property testing, and regularity partitions from
the theory of dense graph limits. These may be of independent interest. In particular
we show that a monotone class of graphs is hyperfinite if and only if it is fractionallytreewidth-fragile and has bounded degree. |
| first_indexed | 2024-03-07T08:11:54Z |
| format | Journal article |
| id | oxford-uuid:f2261c58-7fa8-45bd-bc4c-bd49649c29f6 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T08:11:54Z |
| publishDate | 2023 |
| publisher | Association for Computing Machinery |
| record_format | dspace |
| spelling | oxford-uuid:f2261c58-7fa8-45bd-bc4c-bd49649c29f62023-11-27T09:41:37ZPliability and approximating max-CSPsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:f2261c58-7fa8-45bd-bc4c-bd49649c29f6EnglishSymplectic ElementsAssociation for Computing Machinery2023Romero, MWrochna, MZivny, SWe identify a sufficient condition, treewidth-pliability, that gives a polynomial-time algorithm for an arbitrarily good approximation of the optimal value in a large class of Max-2-CSPs parameterised by the class of allowed constraint graphs (with arbitrary constraints on an unbounded alphabet). Our result applies more generally to the maximum homomorphism problem between two rational-valued structures. The condition unifies the two main approaches for designing a polynomial-time approximation scheme. One is Baker’s layering technique, which applies to sparse graphs such as planar or excluded-minor graphs. The other is based on Szemer´edi’s regularity lemma and applies to dense graphs. We extend the applicability of both techniques to new classes of Max-CSPs. On the other hand, we prove that the condition cannot be used to find solutions (as opposed to approximating the optimal value) in general. Treewidth-pliability turns out to be a robust notion that can be defined in several equivalent ways, including characterisations via size, treedepth, or the Hadwiger number. We show connections to the notions of fractional-treewidth-fragility from structural graph theory, hyperfiniteness from the area of property testing, and regularity partitions from the theory of dense graph limits. These may be of independent interest. In particular we show that a monotone class of graphs is hyperfinite if and only if it is fractionallytreewidth-fragile and has bounded degree. |
| spellingShingle | Romero, M Wrochna, M Zivny, S Pliability and approximating max-CSPs |
| title | Pliability and approximating max-CSPs |
| title_full | Pliability and approximating max-CSPs |
| title_fullStr | Pliability and approximating max-CSPs |
| title_full_unstemmed | Pliability and approximating max-CSPs |
| title_short | Pliability and approximating max-CSPs |
| title_sort | pliability and approximating max csps |
| work_keys_str_mv | AT romerom pliabilityandapproximatingmaxcsps AT wrochnam pliabilityandapproximatingmaxcsps AT zivnys pliabilityandapproximatingmaxcsps |