Conservative constraint satisfaction re-revisited

DOI10.1016/J.JCSS.2015.07.004MaRDI QIDQ896026zbMATH OpenOpenAlexFDO

Authors Andrei A. Bulatov

Publication date 11 December 2015

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1408.3690

zbMATH Keywords

complexityalgebraic approachdichotomyconstraint satisfaction problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Abstract: Conservative constraint satisfaction problems (CSPs) constitute an important particular case of the general CSP, in which the allowed values of each variable can be restricted in an arbitrary way. Problems of this type are well studied for graph homomorphisms. A dichotomy theorem characterizing conservative CSPs solvable in polynomial time and proving that the remaining ones are NP-complete was proved by Bulatov in 2003. Its proof, however, is quite long and technical. A shorter proof of this result based on the absorbing subuniverses technique was suggested by Barto in 2011. In this paper we give a short elementary prove of the dichotomy theorem for the conservative CSP.

Recommendations

• Complexity of conservative constraint satisfaction problems
• Full Constraint Satisfaction Problems
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• CSP for binary conservative relational structures
• A proof of the CSP dichotomy conjecture

Cites work

• scientific article; zbMATH DE number 3751028 (Why is no real title available?)
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• Algorithmic complexity of list colorings
• Bi‐arc graphs and the complexity of list homomorphisms
• Classifying the Complexity of Constraints Using Finite Algebras
• Closure properties of constraints
• Complexity of conservative constraint satisfaction problems
• Constraints, consistency and closure
• Generalized Majority-Minority Operations are Tractable
• List homomorphisms and circular arc graphs
• List homomorphisms to reflexive graphs
• ON THE COMPLEXITY OF SOME MALTSEV CONDITIONS
• On the algebraic structure of combinatorial problems
• On the complexity of H-coloring
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The complexity of satisfiability problems
• Tractability and learnability arising from algebras with few subpowers

Cited in

(20)

• Tractability in constraint satisfaction problems: a survey
• Hardness of Network Satisfaction for Relation Algebras with Normal Representations
• Promise constraint satisfaction: algebraic structure and a symmetric Boolean dichotomy
• The Complexity of Minimal Inference Problem for Conservative Constraint Languages
• Full Constraint Satisfaction Problems
• Every quasitrivial \(n\)-ary semigroup is reducible to a semigroup
• scientific article; zbMATH DE number 7561584 (Why is no real title available?)
• scientific article; zbMATH DE number 7359806 (Why is no real title available?)
• Constants and finite unary relations in qualitative constraint reasoning
• The Complexity of Network Satisfaction Problems for Symmetric Relation Algebras with a Flexible Atom
• Constraint satisfaction problems over semilattice block Mal'tsev algebras
• Aggregation of votes with multiple positions on each issue
• The smallest hard trees
• Graphs of finite algebras: edges, and connectivity
• CSP for binary conservative relational structures
• Complexity of conservative constraint satisfaction problems
• Dichotomies for classes of homomorphism problems involving unary functions
• Absorption in universal algebra and CSP
• The lattice of clones of self-dual operations collapsed
• Algorithmically efficient syntactic characterization of possibility domains

This page was built for publication: Conservative constraint satisfaction re-revisited

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