Maltsev digraphs have a majority polymorphism
From MaRDI portal
Abstract: We prove that when a digraph has a Maltsev polymorphism, then also has a majority polymorphism. We consider the consequences of this result for the structure of Maltsev graphs and the complexity of the Constraint Satisfaction Problem.
Recommendations
Cites work
- A Simple Algorithm for Mal'tsev Constraints
- Classifying the Complexity of Constraints Using Finite Algebras
- Constraint Satisfaction Problems of Bounded Width
- Datalog and Constraint Satisfaction with Infinite Templates
- scientific article; zbMATH DE number 3751028 (Why is no real title available?)
- scientific article; zbMATH DE number 2117181 (Why is no real title available?)
- Majority constraints have bounded pathwidth duality
- On the algebraic structure of combinatorial problems
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
Cited in
(14)- On Maltsev digraphs
- Majority functions on structures with finite duality
- Majority digraphs
- On Maltsev digraphs
- Dualities and algebras with a near-unanimity term
- Reflexive digraphs with near unanimity polymorphisms
- The structure of polynomial operations associated with smooth digraphs.
- scientific article; zbMATH DE number 7359806 (Why is no real title available?)
- Algebra and the complexity of digraph CSPs: a survey
- Quantified Constraints in Twenty Seventeen
- Quantified constraint satisfaction problem on semicomplete digraphs
- Complexity and polymorphisms for digraph constraint problems under some basic constructions
- Binarisation for valued constraint satisfaction problems
- The smallest hard trees
This page was built for publication: Maltsev digraphs have a majority polymorphism
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q627926)
