University of Hertfordshire

From the same journal

By the same authors

On Maltsev digraphs

Research output: Contribution to journalArticle

Documents

  • 905679

    Accepted author manuscript, 333 KB, PDF document

View graph of relations
Original languageEnglish
Pages (from-to)181-194
JournalLecture Notes in Computer Science
Volume6651
DOIs
Publication statusPublished - 2011

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 that the constraint satisfaction problem for Maltsev digraphs is in logspace, L. (This was observed in [19] using an indirect argument.) We then generalize results in [19] 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 G4)-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.

Notes

The original publication is available at www.springerlink.com Copyright Springer

ID: 333306