Treewidth-pliability and PTAS for MAx-CSPS

Miguel Romero, Marcin Wrochna, Stanislav Živný

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

3 Scopus citations


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

Original languageEnglish
Title of host publicationACM-SIAM Symposium on Discrete Algorithms, SODA 2021
EditorsDaniel Marx
PublisherAssociation for Computing Machinery
Number of pages11
ISBN (Electronic)9781611976465
StatePublished - 2021
Externally publishedYes
Event32nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2021 - Alexandria, Virtual, United States
Duration: 10 Jan 202113 Jan 2021

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms


Conference32nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2021
Country/TerritoryUnited States
CityAlexandria, Virtual


Dive into the research topics of 'Treewidth-pliability and PTAS for MAx-CSPS'. Together they form a unique fingerprint.

Cite this