There are no pure relational width 2 constraint satisfaction problems

DOI10.1016/J.IPL.2008.10.005zbMATH Open1191.68339OpenAlexW2123895606MaRDI QIDQ976077FDOQ976077

Authors: Víctor 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

Recommendations

• The collapse of the bounded width hierarchy
• Graphs of relational structures: restricted types
• Bounded width problems and algebras
• On the relational width of first-order expansions of finitely bounded homogeneous binary cores with bounded strict width
• Weak consistency notions for all the CSPs of bounded width

zbMATH Keywords

computational complexityconstraint satisfaction problems

Mathematics Subject Classification ID

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

Cites Work

• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Classifying the Complexity of Constraints Using Finite Algebras
• Recent Results on the Algebraic Approach to the CSP
• Combinatorial problems raised from 2-semilattices
• Title not available (Why is that?)
• Tractability and learnability arising from algebras with few subpowers
• Dualities for Constraint Satisfaction Problems
• Chromatically optimal rigid graphs
• A Subalgebra Intersection Property for Congruence Distributive Varieties
• On tractability and congruence distributivity

Cited In (3)

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

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

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