Conservative constraint satisfaction re-revisited
From MaRDI portal
Publication:896026
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
Cites work
- 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
- scientific article; zbMATH DE number 3751028 (Why is no real title available?)
- List homomorphisms and circular arc graphs
- List homomorphisms to reflexive graphs
- On the algebraic structure of combinatorial problems
- On the complexity of H-coloring
- ON THE COMPLEXITY OF SOME MALTSEV CONDITIONS
- The complexity of satisfiability problems
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- Tractability and learnability arising from algebras with few subpowers
Cited in
(24)- Constants and finite unary relations in qualitative constraint reasoning
- Dichotomies for classes of homomorphism problems involving unary functions
- Every quasitrivial \(n\)-ary semigroup is reducible to a semigroup
- Constraint satisfaction problems over semilattice block Mal'tsev algebras
- CSP for binary conservative relational structures
- Tractability in constraint satisfaction problems: a survey
- Complexity of conservative constraint satisfaction problems
- The Complexity of Minimal Inference Problem for Conservative Constraint Languages
- scientific article; zbMATH DE number 7359806 (Why is no real title available?)
- Absorption in universal algebra and CSP
- scientific article; zbMATH DE number 7561584 (Why is no real title available?)
- Promise constraint satisfaction: algebraic structure and a symmetric Boolean dichotomy
- Hardness of Network Satisfaction for Relation Algebras with Normal Representations
- Algorithmically efficient syntactic characterization of possibility domains
- Aggregation of votes with multiple positions on each issue
- Full Constraint Satisfaction Problems
- The Complexity of Network Satisfaction Problems for Symmetric Relation Algebras with a Flexible Atom
- The smallest hard trees
- The lattice of clones of self-dual operations collapsed
- Graphs of finite algebras: edges, and connectivity
- Network satisfaction problems solved by k-consistency
- Counting list homomorphisms from graphs of bounded treewidth: tight complexity bounds
- Aggregation of evaluations without unanimity
- On the constant-factor approximability of minimum cost constraint satisfaction problems
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)
