Conservative constraint satisfaction re-revisited

DOI10.1016/j.jcss.2015.07.004zbMath1346.68108arXiv1408.3690OpenAlexW1602309302MaRDI QIDQ896026

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

complexityconstraint satisfaction problemdichotomyalgebraic approach

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (14)

Tractability in constraint satisfaction problems: a survey ⋮ Aggregation of Votes with Multiple Positions on Each Issue ⋮ Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy ⋮ Hardness of Network Satisfaction for Relation Algebras with Normal Representations ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The smallest hard trees ⋮ The lattice of clones of self-dual operations collapsed ⋮ Constants and finite unary relations in qualitative constraint reasoning ⋮ Every quasitrivial \(n\)-ary semigroup is reducible to a semigroup ⋮ Constraint satisfaction problems over semilattice block Mal'tsev algebras ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The Complexity of Network Satisfaction Problems for Symmetric Relation Algebras with a Flexible Atom

Cites Work

• Unnamed Item
• On the complexity of H-coloring
• List homomorphisms to reflexive graphs
• Constraints, consistency and closure
• On the algebraic structure of combinatorial problems
• Algorithmic complexity of list colorings
• List homomorphisms and circular arc graphs
• Complexity of conservative constraint satisfaction problems
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• ON THE COMPLEXITY OF SOME MALTSEV CONDITIONS
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Closure properties of constraints
• Bi‐arc graphs and the complexity of list homomorphisms
• Generalized Majority-Minority Operations are Tractable
• Classifying the Complexity of Constraints Using Finite Algebras
• Tractability and Learnability Arising from Algebras with Few Subpowers
• The complexity of satisfiability problems

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