The power of the combined basic linear programming and affine relaxation for promise constraint satisfaction problems

DOI10.1137/20M1312745zbMATH Open1496.68255arXiv1907.04383OpenAlexW3109442675MaRDI QIDQ5138784FDOQ5138784

Authors: Joshua Brakensiek, Marcin Wrochna, S. Zivny, Venkatesan Guruswami 

Publication date: 4 December 2020

Published in: SIAM Journal on Computing (Search for Journal in Brave)

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

Full work available at URL: https://arxiv.org/abs/1907.04383

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

zbMATH Keywords

algorithmslinear programmingCSPlinear equationspolymorphismspromise CSP

Mathematics Subject Classification ID

Linear programming (90C05) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Logic in computer science (03B70) Applications of universal algebra in computer science (08A70) Computational aspects of satisfiability (68R07)

Cites Work

• Graph theory
• Geometric algorithms and combinatorial optimization.
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The complexity of satisfiability problems
• Constraint Satisfaction Problems Solvable by Local Consistency Methods
• A Simple Algorithm for Mal'tsev Constraints
• Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix
• Linear programming, width-1 CSPs, and robust satisfaction
• How to Round Any CSP
• Logical compactness and constraint satisfaction problems
• The power of Sherali-Adams relaxations for general-valued CSPs
• The wonderland of reflections
• \((2+\varepsilon)\)-Sat is NP-hard
• Improved hardness for \(H\)-colourings of \(G\)-colourable graphs
• Promise constraint satisfaction: structure theory and a symmetric Boolean dichotomy
• Algebraic approach to promise constraint satisfaction
• An algorithmic blend of LPs and ring equations for promise CSPs
• Title not available (Why is that?)

Cited In (15)

• 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
• An algorithmic blend of LPs and ring equations for promise CSPs
• Promise constraint satisfaction: algebraic structure and a symmetric Boolean dichotomy
• Sandwiches for promise constraint satisfaction
• 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
• 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)