Treewidth-pliability and PTAS for Max-CSPs

Conference item

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

Authors: Romero, M; Wrochna, M; Zivny, S

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Society for Industrial and Applied Mathematics
• Host title: Proceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms
• Journal: ACM-SIAM Symposium on Discrete Algorithms (SODA21)
• Volume: SODA '21
• Issue: January 2021
• Pages: 473–483
• Publication date: 2021-01-10
• Acceptance date: 2020-09-30
• Event title: ACM-SIAM Symposium on Discrete Algorithms (SODA21)
• Event series: SODA Symposium on Discrete Algorithms
• Event location: Virtual Event Virginia
• Event website: https://dl.acm.org/doi/proceedings/10.5555/3458064
• Event start date: 2021-01-10
• Event end date: 2021-01-13
• Commissioning body: Society for Industrial and Applied Mathematics
• ISBN: 978-1-61197-646-5
• Language: English
• Keywords: FFR