Treewidth-Pliability and PTAS for Max-CSPs
| Autor: | Romero, M., Marcin Wrochna, Živný, S. |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2019 |
| Předmět: |
FOS: Computer and information sciences
Discrete Mathematics (cs.DM) Computer Science - Data Structures and Algorithms FOS: Mathematics Mathematics - Combinatorics Data Structures and Algorithms (cs.DS) Combinatorics (math.CO) G.2.2 F.2.2 16. Peace & justice 68R10 05C75 68W25 68Q17 Computer Science - Discrete Mathematics |
| Zdroj: | Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA) Scopus-Elsevier |
| Popis: | We identify a sufficient condition, treewidth-pliability, that gives a polynomial-time approximation scheme (PTAS) for a large class of Max-2-CSPs parametrised 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 PTASes. One is Baker's layering technique, which applies to sparse graphs such as planar or excluded-minor graphs. The other is based on Szemer\'{e}di's regularity lemma and applies to dense graphs. We extend the applicability of both techniques to new classes of Max-CSPs. 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 fractionally-treewidth-fragile and has bounded degree. Comment: Full version of a SODA'21 paper |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|