Complexity of conservative constraint satisfaction problems

DOI10.1145/1970398.1970400zbMATH Open1351.68113OpenAlexW2032487621WikidataQ130964103 ScholiaQ130964103MaRDI QIDQ2946643FDOQ2946643

Authors: Andrei A. Bulatov 

Publication date: 17 September 2015

Published in: ACM Transactions on Computational Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1970398.1970400

Recommendations

• A proof of the CSP dichotomy conjecture
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• Conservative constraint satisfaction re-revisited
• Asking the Metaquestions in Constraint Tractability
• scientific article; zbMATH DE number 1670830

zbMATH Keywords

complexityconstraint satisfaction problemdichotomy theoremhomomorphism problem

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15)

Cited In (61)

• Surjective \texttt{H}-colouring over reflexive digraphs
• Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms
• The complexity of surjective homomorphism problems-a survey
• Promise constraint satisfaction: algebraic structure and a symmetric Boolean dichotomy
• Tractability in constraint satisfaction problems: a survey
• The Complexity of Minimal Inference Problem for Conservative Constraint Languages
• The power of linear programming for general-valued CSPs
• Time complexity of constraint satisfaction via universal algebra
• Title not available (Why is that?)
• Title not available (Why is that?)
• Dichotomy for finite tournaments of mixed-type
• Qualitative constraint satisfaction problems: an extended framework with landmarks
• On the computational complexity of non-dictatorial aggregation
• Conservative constraint satisfaction re-revisited
• Constant-query testability of assignments to constraint satisfaction problems
• Algebraic properties of valued constraint satisfaction problem
• List homomorphisms to separable signed graphs
• Minimum cost homomorphisms with constrained costs
• The power of Sherali-Adams relaxations for general-valued CSPs
• Constraint satisfaction problems over semilattice block Mal'tsev algebras
• The property of being polynomial for Mal’tsev constraint satisfaction problems
• The complexity of constraint satisfaction revisited
• Testing the Complexity of a Valued CSP Language
• Aggregation of votes with multiple positions on each issue
• Consistent query answering for primary keys in Datalog
• Binarisation for valued constraint satisfaction problems
• The complexity of general-valued CSPs
• Minimax problems of discrete optimization invariant under majority operators
• Necessary conditions for tractability of valued CSPs
• Dichotomy for tree-structured trigraph list homomorphism problems
• Adjusted interval digraphs
• A proof of the CSP dichotomy conjecture
• Title not available (Why is that?)
• A Galois connection for valued constraint languages of infinite size
• Complexity of infinite-domain constraint satisfaction
• On planar valued CSPs
• Bounded Tree-Width and CSP-Related Problems
• CSP for binary conservative relational structures
• Digraph matrix partitions and trigraph homomorphisms
• The complexity of valued CSPs
• Hard constraint satisfaction problems have hard gaps at location 1
• Hybrid VCSPs with crisp and valued conservative templates
• Absorption in universal algebra and CSP
• Algebra and the complexity of digraph CSPs: a survey
• Title not available (Why is that?)
• The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side
• Correspondence homomorphisms to reflexive graphs
• Complexity of correspondence \(H\)-colourings
• A quasi-Mal'cev condition with unexpected application.
• Constraint satisfaction problems: convexity makes AllDifferent constraints tractable
• A dichotomy for minimum cost graph homomorphisms
• Minimum cost and list homomorphisms to semicomplete digraphs
• Dynamic algorithms for classes of constraint satisfaction problems
• Gap theorems for robust satisfiability: Boolean CSPs and beyond
• Unifying the three algebraic approaches to the CSP via minimal Taylor algebras
• Title not available (Why is that?)
• CSP beyond tractable constraint languages
• The complexity of the distributed constraint satisfaction problem
• Graphs of finite algebras: maximality, rectangularity, and decomposition
• Graphs of finite algebras: edges, and connectivity
• Towards a dichotomy for the list switch homomorphism problem for signed graphs

This page was built for publication: Complexity of conservative constraint satisfaction problems

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