Solving CSPs using weak local consistency

DOI10.1137/18M117577XMaRDI QIDQ5009788zbMATH OpenOpenAlexFDO

Authors Marcin Kozik

Publication date 6 August 2021

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/18m117577x

zbMATH Keywords

algebraic approach to CSPconstraint satisfaction problemlocal consistency

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Descriptive complexity and finite models (68Q19) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Weak consistency notions for all the CSPs of bounded width
• Constraint Satisfaction Problems Solvable by Local Consistency Methods
• On singleton arc consistency for CSPs defined by monotone patterns
• On singleton arc consistency for CSPs defined by monotone patterns
• scientific article; zbMATH DE number 1487982

Cites work

• A characterization of idempotent strong Mal'cev conditions for congruence meet-semidistributivity in locally finite varieties
• Algebraic approach to promise constraint satisfaction
• Arc consistency and friends
• Bounded width problems and algebras
• Classifying the Complexity of Constraints Using Finite Algebras
• Constraint Satisfaction Problems of Bounded Width
• Constraint Satisfaction Problems Solvable by Local Consistency Methods
• Dualities for Constraint Satisfaction Problems
• scientific article; zbMATH DE number 1670830 (Why is no real title available?)
• scientific article; zbMATH DE number 1487982 (Why is no real title available?)
• scientific article; zbMATH DE number 5485593 (Why is no real title available?)
• scientific article; zbMATH DE number 6783493 (Why is no real title available?)
• scientific article; zbMATH DE number 3336786 (Why is no real title available?)
• Majority constraints have bounded pathwidth duality
• Mal'tsev conditions, lack of absorption, and solvability.
• Maltsev families of varieties closed under join or Maltsev product
• Near unanimity constraints have bounded pathwidth duality
• Peek arc consistency
• Promise constraint satisfaction: structure theory and a symmetric Boolean dichotomy
• Robust algorithms with polynomial loss for near-unanimity CSPs
• Robust satisfiability for CSPs: hardness and algorithmic results
• Robust satisfiability of constraint satisfaction problems
• Robustly solvable constraint satisfaction problems
• The collapse of the bounded width hierarchy
• The complexity of satisfiability problems
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The structure of finite algebras
• Theoretical analysis of singleton arc consistency and its extensions
• Weak consistency notions for all the CSPs of bounded width

Cited in

(12)

• Decidability of absorption in relational structures of bounded width.
• Computing weak consistency in polynomial time (extended abstract)
• Local Symmetry Breaking During Search in CSPs
• Congruence distributivity implies bounded width
• scientific article; zbMATH DE number 1487982 (Why is no real title available?)
• Weak consistency notions for all the CSPs of bounded width
• CLAP: A New Algorithm for Promise CSPs
• Unifying the three algebraic approaches to the CSP via minimal Taylor algebras
• The complexity of the distributed constraint satisfaction problem
• Quantum advantage and CSP complexity
• Quantum advantage and CSP complexity
• Satisfiability of commutative vs. non-commutative CSPs

This page was built for publication: Solving CSPs using weak local consistency

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