PTAS for Sparse General-valued CSPs
From MaRDI portal
Abstract: We study polynomial-time approximation schemes (PTASes) for constraint satisfaction problems (CSPs) such as Maximum Independent Set or Minimum Vertex Cover on sparse graph classes. Baker's approach gives a PTAS on planar graphs, excluded-minor classes, and beyond. For Max-CSPs, and even more generally, maximisation finite-valued CSPs (where constraints are arbitrary non-negative functions), Romero, Wrochna, and v{Z}ivn'y [SODA'21] showed that the Sherali-Adams LP relaxation gives a simple PTAS for all fractionally-treewidth-fragile classes, which is the most general "sparsity" condition for which a PTAS is known. We extend these results to general-valued CSPs, which include "crisp" (or "strict") constraints that have to be satisfied by every feasible assignment. The only condition on the crisp constraints is that their domain contains an element which is at least as feasible as all the others (but possibly less valuable). For minimisation general-valued CSPs with crisp constraints, we present a PTAS for all Baker graph classes -- a definition by Dvov{r}'ak [SODA'20] which encompasses all classes where Baker's technique is known to work, except possibly for fractionally-treewidth-fragile classes. While this is standard for problems satisfying a certain monotonicity condition on crisp constraints, we show this can be relaxed to diagonalisability -- a property of relational structures connected to logics, statistical physics, and random CSPs.
Cites work
- A dichotomy for minimum cost graph homomorphisms
- A dichotomy theorem for the general minimum cost homomorphism problem
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- A linear time algorithm for finding tree-decompositions of small treewidth
- A partial k-arboretum of graphs with bounded treewidth
- Algebraic properties of valued constraint satisfaction problem
- Algorithms for graphs embeddable with few crossings per edge
- Approximation Algorithms for CSPs
- Approximation algorithms for NP-complete problems on planar graphs
- Approximation of minimum cost homomorphisms
- Baker game and polynomial-time approximation schemes
- Complexity and approximability of quantified and stochastic constraint satisfaction problems
- Dismantlability, connectedness, and mixing in relational structures
- Dualities for Constraint Satisfaction Problems
- Excluding any graph as a minor allows a low tree-width 2-coloring
- Gibbs measures and dismantlable graphs
- Graph theory
- Hard constraint satisfaction problems have hard gaps at location 1
- scientific article; zbMATH DE number 5485536 (Why is no real title available?)
- scientific article; zbMATH DE number 1256750 (Why is no real title available?)
- scientific article; zbMATH DE number 1944139 (Why is no real title available?)
- scientific article; zbMATH DE number 7561584 (Why is no real title available?)
- Hybrid tractable classes of constraint problems
- Introduction to the Maximum Solution Problem
- Linear degree extractors and the inapproximability of max clique and chromatic number
- Local tree-width, excluded minors, and approximation algorithms
- MAX ONES Generalized to Larger Domains
- NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
- On fractional fragility rates of graph classes
- On LP-based approximability for strict CSPs
- On the power of unique 2-prover 1-round games
- Sublinear separators, fragility and subexponential expansion
- The approximability of constraint satisfaction problems
- The Complexity of Boolean Surjective General-Valued CSPs
- The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side
- The complexity of general-valued CSPs
- The complexity of homomorphism and constraint satisfaction problems seen from the other side
- The complexity of valued constraint satisfaction
- The dichotomy of minimum cost homomorphism problems for digraphs
- Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete
- When is the evaluation of conjunctive queries tractable?
This page was built for publication: PTAS for Sparse General-valued CSPs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6075749)
