There are no pure relational width 2 constraint satisfaction problems

DOI10.1016/j.ipl.2008.10.005zbMath1191.68339OpenAlexW2123895606MaRDI QIDQ976077

Victor Dalmau

Publication date: 16 June 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2008.10.005

zbMATH Keywords

computational complexityconstraint satisfaction problems

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (3)

CLAP: A New Algorithm for Promise CSPs ⋮ The Power of Sherali--Adams Relaxations for General-Valued CSPs ⋮ Dualities for Constraint Satisfaction Problems

Cites Work

• Unnamed Item
• Chromatically optimal rigid graphs
• Combinatorial problems raised from 2-semilattices
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• A Subalgebra Intersection Property for Congruence Distributive Varieties
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• On tractability and congruence distributivity
• Classifying the Complexity of Constraints Using Finite Algebras
• Tractability and Learnability Arising from Algebras with Few Subpowers
• Recent Results on the Algebraic Approach to the CSP
• Dualities for Constraint Satisfaction Problems

This page was built for publication: There are no pure relational width 2 constraint satisfaction problems