There are no pure relational width 2 constraint satisfaction problems

DOI10.1016/J.IPL.2008.10.005MaRDI QIDQ976077zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

computational complexityconstraint satisfaction problems

Mathematics Subject Classification ID

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

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

Cites work

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

Cited in

(4)

• The power of Sherali-Adams relaxations for general-valued CSPs
• CLAP: A New Algorithm for Promise CSPs
• Dualities for Constraint Satisfaction Problems
• On the relational width of first-order expansions of finitely bounded homogeneous binary cores with bounded strict width

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)