Small Promise CSPs that reduce to large CSPs

DOI10.46298/lmcs-18(3:25)2022OpenAlexW4292723075MaRDI QIDQ5043583

Alexandr Kazda, Dmitriy N. Zhuk, Peter Mayr

Publication date: 6 October 2022

Published in: Logical Methods in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

sandwichdigraphconstraint satisfaction problempromise constraint satisfaction problemrelational structure homomorphism

Mathematics Subject Classification ID

Logic in computer science (03B70) Computer science (68-XX)

Cites Work

• Unnamed Item
• Unnamed Item
• On the complexity of H-coloring
• Sandwiches for promise constraint satisfaction
• Absorbing Subalgebras, Cyclic Terms, and the Constraint Satisfaction Problem
• The Complexity of Near-Optimal Graph Coloring
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Algebraic Approach to Promise Constraint Satisfaction
• $(2+\varepsilon)$-Sat Is NP-hard
• The complexity of satisfiability problems