TY - GEN

T1 - Treewidth-pliability and PTAS for MAx-CSPS

AU - Romero, Miguel

AU - Wrochna, Marcin

AU - Živný, Stanislav

N1 - Funding Information:
Stanislav Živný was supported by a Royal Society University Research Fellowship. Work done while Miguel Romero was at the University of Oxford. This project has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No 714532). The paper reflects only the authors' views and not the views of the ERC or the European Commission. The European Union is not liable for any use that may be made of the information contained therein.
Funding Information:
∗StanislavZˇivny´ was supportedbyaRoyal SocietyUniversity ResearchFellowship. Work donewhileMiguelRomerowas at theUniversity of Oxford. Thisprojecthasreceived funding fromtheEuropeanResearchCouncil(ERC) undertheEuropean Union’sHorizon2020researchandinnovation programme(grant agreementNo714532). Thepaperreflectsonlytheauthors’views andnottheviewsoftheERCortheEuropeanCommission. The EuropeanUnionisnotliableforanyusethatmaybemadeofthe informationcontained therein.
Publisher Copyright:
Copyright © 2021 by SIAM

PY - 2021

Y1 - 2021

N2 - 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é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. The full version [59] containing detailed proofs is available at https://arxiv.org/abs/1911.03204.

AB - 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é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. The full version [59] containing detailed proofs is available at https://arxiv.org/abs/1911.03204.

UR - http://www.scopus.com/inward/record.url?scp=85100478737&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85100478737

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 473

EP - 483

BT - ACM-SIAM Symposium on Discrete Algorithms, SODA 2021

A2 - Marx, Daniel

PB - Association for Computing Machinery

T2 - 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2021

Y2 - 10 January 2021 through 13 January 2021

ER -