Complexity of conservative constraint satisfaction problems

DOI10.1145/1970398.1970400MaRDI QIDQ2946643zbMATH OpenOpenAlexWikidataFDO

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

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)

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

Cited in

(61)

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

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)