Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

PTAS for Sparse General-valued CSPs

PTAS for Sparse General-valued CSPs 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 Živný [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 that 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 Dvořák [SODA’20] that encompasses all classes where Baker’s technique is known to work, except 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. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Algorithms (TALG) Association for Computing Machinery

PTAS for Sparse General-valued CSPs

Download PDF
31 pages

Loading next page...
 
/lp/association-for-computing-machinery/ptas-for-sparse-general-valued-csps-EQWxfU2eb1

References

References for this paper are not available at this time. We will be adding them shortly, thank you for your patience.

Publisher
Association for Computing Machinery
Copyright
Copyright © 2023 Association for Computing Machinery.
ISSN
1549-6325
eISSN
1549-6333
DOI
10.1145/3569956
Publisher site
See Article on Publisher Site

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 Živný [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 that 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 Dvořák [SODA’20] that encompasses all classes where Baker’s technique is known to work, except 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.

Journal

ACM Transactions on Algorithms (TALG) – Association for Computing Machinery

Published: Mar 9, 2023

Keywords: Constraint satisfaction

References

  • Approximation algorithms for NP-complete problems on planar graphs
    [,
  • On some tighter inapproximability results (extended abstract)
    [,
  • A linear time algorithm for finding tree-decompositions of small treewidth
    [,
  • A partial k-arboretum of graphs with bounded treewidth
    [,
  • Dismantlability, connectedness, and mixing in relational structures
    [,
  • Gibbs measures and dismantlable graphs
    [,
  • Dualities for constraint satisfaction problems
    [,
  • The complexity of general-valued constraint satisfaction problems seen from the other side
    [,
  • Hybrid tractable classes of constraint problems
    [,
  • Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete
    [,
  • Algorithmic graph minor theory: Decomposition, approximation, and coloring
    [,
  • Excluding any graph as a minor allows a low tree-width 2-coloring
    [,
  • Graph Theory (4th ed
    [,
  • Personal communication
    [,
  • Sublinear separators, fragility and subexponential expansion
    [,
  • Baker game and polynomial-time approximation schemes
    [,
  • On fractional fragility rates of graph classes
    [,
  • The complexity of Boolean surjective general-valued CSPs
    [,
  • Algorithms for graphs embeddable with few crossings per edge
    [,
  • Local tree-width, excluded minors, and approximation algorithms
    [,
  • The complexity of homomorphism and constraint satisfaction problems seen from the other side
    [,
  • When is the evaluation of conjunctive queries tractable? In Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (STOC’01)
    [,
  • A dichotomy for minimum cost graph homomorphisms
    [,
  • Approximation of minimum cost homomorphisms
    [,
  • The dichotomy of minimum cost homomorphism problems for digraphs
    [,
  • NC-approximation schemes for NP- and PSPACE-hard problems for geometric graphs
    [,
  • The complexity of valued constraint satisfaction
    [,
  • Hard constraint satisfaction problems have hard gaps at location 1
    [,
  • MAX ONES generalized to larger domains
    [,
  • Introduction to the maximum solution problem
    [,
  • Towards a syntactic characterization of PTAS
    [,
  • The approximability of constraint satisfaction problems
    [,
  • On the power of unique 2-prover 1-round games
    [,
  • The complexity of general-valued CSPs
    [,
  • Algebraic properties of valued constraint satisfaction problem
    [,
  • On LP-based approximability for strict CSPs
    [,
  • Approximation algorithms for CSPs
    [,
  • Level-treewidth property, exact algorithms and approximation schemes
    [,
  • PTAS for sparse general-valued CSPs
    [,
  • Toward a dichotomy for approximation of H-Coloring
    [,
  • Optimal algorithms and inapproximability results for every CSP? In Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC’08)
    [,
  • Algorithmic aspects of tree width
    [,
  • Treewidth-Pliability and PTAS for Max-CSPs
    [,
  • Treewidth-pliability and PTAS for Max-CSPs
    [,
  • A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems
    [,
  • A dichotomy theorem for the general minimum cost homomorphism problem
    [,
  • Linear degree extractors and the inapproximability of max clique and chromatic number
    [,