We study digraphs preserved by a Maltsev operation: Maltsev digraphs. We show that these digraphs retract either onto a directed path or to the disjoint union of directed cycles, showing in this way that the constraint satisfaction problem for Maltsev digraphs is in logspace, L. We then generalize results from Kazda (2011) to show that a Maltsev digraph is preserved not only by a majority operation, but by a class of other operations (e.g., minority, Pixley) and obtain a $O(|V_G|^4)$-time algorithm to recognize Maltsev digraphs. We also prove analogous results for digraphs preserved by conservative Maltsev operations which we use to establish that the list homomorphism problem for Maltsev digraphs is in L. We then give a polynomial time characterisation of Maltsev digraphs admitting a conservative 2-semilattice operation. Finally, we give a simple inductive construction of directed acyclic digraphs preserved by a Maltsev operation, and relate them with series parallel digraphs.
@article{10_37236_4419,
author = {Catarina Carvalho and Laszlo Egri and Marcel Jackson and Todd Niven},
title = {On {Maltsev} digraphs},
journal = {The electronic journal of combinatorics},
year = {2015},
volume = {22},
number = {1},
doi = {10.37236/4419},
zbl = {1308.05053},
url = {http://geodesic.mathdoc.fr/articles/10.37236/4419/}
}
TY - JOUR
AU - Catarina Carvalho
AU - Laszlo Egri
AU - Marcel Jackson
AU - Todd Niven
TI - On Maltsev digraphs
JO - The electronic journal of combinatorics
PY - 2015
VL - 22
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/4419/
DO - 10.37236/4419
ID - 10_37236_4419
ER -
%0 Journal Article
%A Catarina Carvalho
%A Laszlo Egri
%A Marcel Jackson
%A Todd Niven
%T On Maltsev digraphs
%J The electronic journal of combinatorics
%D 2015
%V 22
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/4419/
%R 10.37236/4419
%F 10_37236_4419
Catarina Carvalho; Laszlo Egri; Marcel Jackson; Todd Niven. On Maltsev digraphs. The electronic journal of combinatorics, Tome 22 (2015) no. 1. doi: 10.37236/4419
