Conservative constraint satisfaction re-revisited
From MaRDI portal
Publication:896026
DOI10.1016/J.JCSS.2015.07.004zbMATH Open1346.68108arXiv1408.3690OpenAlexW1602309302MaRDI QIDQ896026FDOQ896026
Authors: Andrei A. Bulatov 
Publication date: 11 December 2015
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1408.3690
Recommendations
Cites Work
- On the complexity of H-coloring
- A dichotomy theorem for constraint satisfaction problems on a 3-element set
- Title not available (Why is that?)
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- Closure properties of constraints
- Classifying the Complexity of Constraints Using Finite Algebras
- The complexity of satisfiability problems
- Constraints, consistency and closure
- On the algebraic structure of combinatorial problems
- Complexity of conservative constraint satisfaction problems
- Generalized Majority-Minority Operations are Tractable
- Tractability and learnability arising from algebras with few subpowers
- List homomorphisms and circular arc graphs
- List homomorphisms to reflexive graphs
- Bi‐arc graphs and the complexity of list homomorphisms
- ON THE COMPLEXITY OF SOME MALTSEV CONDITIONS
- Algorithmic complexity of list colorings
Cited In (20)
- Hardness of Network Satisfaction for Relation Algebras with Normal Representations
- 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
- Full Constraint Satisfaction Problems
- Title not available (Why is that?)
- Title not available (Why is that?)
- Every quasitrivial \(n\)-ary semigroup is reducible to a semigroup
- 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)
