Algebraic approach to promise constraint satisfaction

DOI10.1145/3313276.3316300MaRDI QIDQ5212802zbMATH OpenOpenAlexFDO

Authors Jakub Bulín, Andrei Krokhin, Jakub Opršal

Publication date 30 January 2020

Published in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

approximationconstraint satisfactionpolymorphismgraph colouringpromise problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15) Computational aspects of satisfiability (68R07)

Abstract: The complexity and approximability of the constraint satisfaction problem (CSP) has been actively studied over the last 20 years. A new version of the CSP, the promise CSP (PCSP) has recently been proposed, motivated by open questions about the approximability of variants of satisfiability and graph colouring. The PCSP significantly extends the standard decision CSP. The complexity of CSPs with a fixed constraint language on a finite domain has recently been fully classified, greatly guided by the algebraic approach, which uses polymorphisms --- high-dimensional symmetries of solution spaces --- to analyse the complexity of problems. The corresponding classification for PCSPs is wide open and includes some long-standing open questions, such as the complexity of approximate graph colouring, as special cases. The basic algebraic approach to PCSP was initiated by Brakensiek and Guruswami, and in this paper we significantly extend it and lift it from concrete properties of polymorphisms to their abstract properties. We introduce a new class of problems that can be viewed as algebraic versions of the (Gap) Label Cover problem, and show that every PCSP with a fixed constraint language is equivalent to a problem of this form. This allows us to identify a "measure of symmetry" that is well suited for comparing and relating the complexity of different PCSPs via the algebraic approach. We demonstrate how our theory can be applied by improving the state-of-the-art in approximate graph colouring: we show that, for any $kgeq3$, it is NP-hard to find a $(2k-1)$-colouring of a given $k$-colourable graph.

Recommendations

• Algebraic Approach to Promise Constraint Satisfaction
• Promise constraint satisfaction: algebraic structure and a symmetric Boolean dichotomy
• Promise constraint satisfaction: structure theory and a symmetric Boolean dichotomy
• The power of the combined basic linear programming and affine relaxation for promise constraint satisfaction problems
• The complexity of promise SAT on non-Boolean domains

Cited in

(28)

• Algebraic Approach to Promise Constraint Satisfaction
• Promise constraint satisfaction: structure theory and a symmetric Boolean dichotomy
• Coloring tournaments with few colors: algorithms and complexity
• The lattice and semigroup structure of multipermutations
• Closed sets of finitary functions between products of finite fields of coprime order
• Rainbow coloring hardness via low sensitivity polymorphisms
• scientific article; zbMATH DE number 7561683 (Why is no real title available?)
• Geometric, algebraic and topological combinatorics. Abstracts from the workshop held December 10--15, 2023
• An algorithmic blend of LPs and ring equations for promise CSPs
• Accessible set functors are universal
• The power of the combined basic linear programming and affine relaxation for promise constraint satisfaction problems
• Pseudo‐loop conditions
• Revisiting alphabet reduction in Dinur’s PCP.
• Max-3-Lin over non-abelian groups with universal factor graphs
• Solving CSPs using weak local consistency
• Smooth digraphs modulo primitive positive constructability and cyclic loop conditions
• Nonfinitely based ai-semirings with finitely based semigroup reducts
• Closed sets of finitary functions between finite fields of coprime order
• Topology and Adjunction in Promise Constraint Satisfaction
• Promise constraint satisfaction: algebraic structure and a symmetric Boolean dichotomy
• \( \omega \)-categorical structures avoiding height 1 identities
• scientific article; zbMATH DE number 7561550 (Why is no real title available?)
• The algebraic structure of the densification and the sparsification tasks for CSPs
• Constraint satisfaction problem: what makes the problem easy
• Near-unanimity-closed minions of Boolean functions
• Reflections and powers of multisorted minions
• Sandwiches for promise constraint satisfaction
• The combined basic LP and affine IP relaxation for promise VCSPs on infinite domains

This page was built for publication: Algebraic approach to promise constraint satisfaction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5212802)