The power of the combined basic linear programming and affine relaxation for promise constraint satisfaction problems
From MaRDI portal
Publication:5138784
Abstract: In the field of constraint satisfaction problems (CSP), promise CSPs are an exciting new direction of study. In a promise CSP, each constraint comes in two forms: "strict" and "weak," and in the associated decision problem one must distinguish between being able to satisfy all the strict constraints versus not being able to satisfy all the weak constraints. The most commonly cited example of a promise CSP is the approximate graph coloring problem--which has recently seen exciting progress [BKO19, WZ20] benefiting from a systematic algebraic approach to promise CSPs based on "polymorphisms," operations that map tuples in the strict form of each constraint to tuples in the corresponding weak form. In this work, we present a simple algorithm which in polynomial time solves the decision problem for all promise CSPs that admit infinitely many symmetric polymorphisms, which are invariant under arbitrary coordinate permutations. This generalizes previous work of the first two authors [BG19]. We also extend this algorithm to a more general class of block-symmetric polymorphisms. As a corollary, this single algorithm solves all polynomial-time tractable Boolean CSPs simultaneously. These results give a new perspective on Schaefer's classic dichotomy theorem and shed further light on how symmetries of polymorphisms enable algorithms. Finally, we show that block symmetric polymorphisms are not only sufficient but also necessary for this algorithm to work, thus establishing its precise power
Recommendations
- An algorithmic blend of LPs and ring equations for promise CSPs
- Promise constraint satisfaction: algebraic structure and a symmetric Boolean dichotomy
- Promise constraint satisfaction: structure theory and a symmetric Boolean dichotomy
- Algebraic Approach to Promise Constraint Satisfaction
- Algebraic approach to promise constraint satisfaction
Cites work
- scientific article; zbMATH DE number 7561550 (Why is no real title available?)
- A Simple Algorithm for Mal'tsev Constraints
- Algebraic approach to promise constraint satisfaction
- An algorithmic blend of LPs and ring equations for promise CSPs
- Constraint Satisfaction Problems Solvable by Local Consistency Methods
- Geometric algorithms and combinatorial optimization.
- Graph theory
- How to Round Any CSP
- Improved hardness for \(H\)-colourings of \(G\)-colourable graphs
- Linear programming, width-1 CSPs, and robust satisfaction
- Logical compactness and constraint satisfaction problems
- Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix
- Promise constraint satisfaction: structure theory and a symmetric Boolean dichotomy
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- The complexity of satisfiability problems
- The power of Sherali-Adams relaxations for general-valued CSPs
- The wonderland of reflections
- \((2+\varepsilon)\)-Sat is NP-hard
Cited in
(16)- Beyond PCSP (\textbf{1-in-3}, \textbf{NAE})
- Local–global property for G-invariant terms
- Conditional dichotomy of Boolean ordered promise CSPs
- Promise constraint satisfaction: structure theory and a symmetric Boolean dichotomy
- Sandwiches for promise constraint satisfaction
- An algorithmic blend of LPs and ring equations for promise CSPs
- Promise constraint satisfaction: algebraic structure and a symmetric Boolean dichotomy
- CLAP: a new algorithm for promise CSPs
- CLAP: A New Algorithm for Promise CSPs
- Topology and Adjunction in Promise Constraint Satisfaction
- The combined basic LP and affine IP relaxation for promise VCSPs on infinite domains
- The Combined Basic LP and Affine IP Relaxation for Promise VCSPs on Infinite Domains
- Algebraic Approach to Promise Constraint Satisfaction
- Algebraic approach to promise constraint satisfaction
- Approximate graph colouring and the hollow shadow
- SDPs and robust satisfiability of promise CSP
This page was built for publication: The power of the combined basic linear programming and affine relaxation for promise constraint satisfaction problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5138784)
