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

(66)

• Dynamic algorithms for classes of constraint satisfaction problems
• Surjective \texttt{H}-colouring over reflexive digraphs
• Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms
• The complexity of surjective homomorphism problems-a survey
• Unifying the three algebraic approaches to the CSP via minimal Taylor algebras
• Tractability in constraint satisfaction problems: a survey
• Promise constraint satisfaction: algebraic structure and a symmetric Boolean dichotomy
• scientific article; zbMATH DE number 7536562 (Why is no real title available?)
• The Complexity of Minimal Inference Problem for Conservative Constraint Languages
• Counting list homomorphisms from graphs of bounded treewidth: tight complexity bounds
• The power of linear programming for general-valued CSPs
• Time complexity of constraint satisfaction via universal algebra
• Dichotomy for finite tournaments of mixed-type
• scientific article; zbMATH DE number 7561584 (Why is no real title available?)
• scientific article; zbMATH DE number 7359806 (Why is no real title available?)
• Qualitative constraint satisfaction problems: an extended framework with landmarks
• CSP beyond tractable constraint languages
• Conservative constraint satisfaction re-revisited
• On the computational complexity of non-dictatorial aggregation
• Constant-query testability of assignments to constraint satisfaction problems
• Algebraic properties of valued constraint satisfaction problem
• Minimum cost homomorphisms with constrained costs
• Constraint satisfaction problems over semilattice block Mal'tsev algebras
• List homomorphisms to separable signed graphs
• The power of Sherali-Adams relaxations for general-valued CSPs
• The property of being polynomial for Mal’tsev constraint satisfaction problems
• Solving promise equations over monoids and groups
• The complexity of constraint satisfaction revisited
• Network satisfaction problems solved by k-consistency
• Testing the Complexity of a Valued CSP Language
• Consistent query answering for primary keys in Datalog
• Aggregation of votes with multiple positions on each issue
• The complexity of the distributed constraint satisfaction problem
• 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
• Aggregation of evaluations without unanimity
• Adjusted interval digraphs
• Graphs of finite algebras: maximality, rectangularity, and decomposition
• Graphs of finite algebras: edges, and connectivity
• scientific article; zbMATH DE number 4162262 (Why is no real title available?)
• A proof of the CSP dichotomy conjecture
• A Galois connection for valued constraint languages of infinite size
• Complexity of infinite-domain constraint satisfaction
• On planar valued CSPs
• CSP for binary conservative relational structures
• Solving promise equations over monoids and groups
• Towards a dichotomy for the list switch homomorphism problem for signed graphs
• Bounded Tree-Width and CSP-Related Problems
• 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
• Correspondence homomorphisms to reflexive graphs
• Complexity of correspondence \(H\)-colourings
• scientific article; zbMATH DE number 7561483 (Why is no real title available?)
• The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side
• 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
• Gap theorems for robust satisfiability: Boolean CSPs and beyond

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)