University of Hertfordshire

By the same authors

On Maltsev Digraphs

Research output: Research - peer-reviewArticle

Documents

  • 907164

    Final published version, 425 KB, PDF-document

Links

View graph of relations
Original languageEnglish
Article number1.47
Number of pages32
JournalElectronic Journal of Combinatorics
Journal publication date25 Feb 2015
Volume22
Issue1
StatePublished - 25 Feb 2015

Abstract

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(|VG|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.

Notes

Date of Acceptance: 05/02/2015

ID: 9216583