Algebraic approach to promise constraint satisfaction

DOI10.1145/3313276.3316300zbMATH Open1433.68271arXiv1811.00970OpenAlexW3007452340MaRDI QIDQ5212802FDOQ5212802

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)

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.

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

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

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)

Cited In (28)

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

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)