\documentclass[12pt]{article}

\usepackage{e-jc}
\specs{P1.47}{22(1)}{2015}

\usepackage{mathenv, amssymb, amsmath, verbatim, graphicx, url,epstopdf, amsthm}

%\setcounter{tocdepth}{3}

%\urldef{\mailsa}\path|laszlo.egri@mail.mcgill.ca|
%\newcommand{\keywords}[1]{\par\addvspace\baselineskip
%\noindent\keywordname\enspace\ignorespaces#1}

\DeclareMathOperator*{\CSP}{CSP}
\newcommand{\up}[1]{\textup{#1}}
\newcommand{\id}{\operatorname{id}}
\newcommand{\bea}{\begin{eqnarray*}}
\newcommand{\eea}{\end{eqnarray*}}
\newcommand{\perm}{\operatorname{p}}
\newcommand{\fix}{\operatorname{fix}}
\newcommand{\Rep}{\operatorname{Rep}}
\newcommand{\Id}{\operatorname{Id}}
%
\newcommand{\ben}{\begin{enumerate}}
\newcommand{\een}{\end{enumerate}}
\newcommand{\dom}{\operatorname{dom}}
\newcommand{\ran}{\operatorname{ran}}
%
\newcommand{\har}{\hspace{-1.5mm}\upharpoonright}
\newcommand{\vor}{\mathbin{\vee\kern -8.5truept \vee}}%bd's macro
\newcommand{\bigor}{\mathop{\bigvee\kern -8.5truept \bigvee}}%bd's macro
\newcommand{\Bigand}{\operatornamewithlimits{\hbox{\LARGE$\&$}}}
\newcommand{\bigand}{\operatornamewithlimits{\hbox{\large$\&$}}}
%
\newcommand{\N}{\ensuremath{\nabla}}
\newcommand{\rN}{\ensuremath{\Delta}}
\newcommand{\bbN}{\mathbb{N}}
\newcommand{\bbZ}{\mathbb{Z}}
\newcommand{\ccL}{\ensuremath{\mathsf{L}}}
\newcommand{\ccNL}{\ensuremath{\mathsf{NL}}}
\newcommand{\ccP}{\ensuremath{\mathsf{P}}}
\newcommand{\ccNP}{\ensuremath{\mathsf{NP}}}
\newcommand{\ccLHOM}{\ensuremath{\mathsf{LHOM}}}

\newcommand{\zed}{\mathbb{Z}}% Z

%SHORTCUTS FOR MATHBF
\newcommand{\bA}{\mathbf{A}}
\newcommand{\bB}{\mathbf{B}}
\newcommand{\bC}{\mathbf{C}}
\newcommand{\bD}{\mathbf{D}}
\newcommand{\bE}{\mathbf{E}}
\newcommand{\bF}{\mathbf{F}}
\newcommand{\bG}{\mathbf{G}}
\newcommand{\bH}{\mathbf{H}}
\newcommand{\bI}{\mathbf{I}}
\newcommand{\bJ}{\mathbf{J}}
\newcommand{\bK}{\mathbf{K}}
\newcommand{\bL}{\mathbf{L}}
\newcommand{\bM}{\mathbf{M}}
\newcommand{\bN}{\mathbf{N}}
\newcommand{\bO}{\mathbf{O}}
\newcommand{\bP}{\mathbf{P}}
\newcommand{\bQ}{\mathbf{Q}}
\newcommand{\bR}{\mathbf{R}}
\newcommand{\bS}{\mathbf{S}}
\newcommand{\bT}{\mathbf{T}}
\newcommand{\bU}{\mathbf{U}}
\newcommand{\bV}{\mathbf{V}}
\newcommand{\bW}{\mathbf{W}}
\newcommand{\bX}{\mathbf{X}}
\newcommand{\bY}{\mathbf{Y}}
\newcommand{\bZ}{\mathbf{Z}}

%SHORTCUTS FOR MATHCAL
\newcommand{\cA}{\mathcal{A}}
\newcommand{\cB}{\mathcal{B}}
\newcommand{\cC}{\mathcal{C}}
\newcommand{\cD}{\mathcal{D}}
\newcommand{\cE}{\mathcal{E}}
\newcommand{\cF}{\mathcal{F}}
\newcommand{\cG}{\mathcal{G}}
\newcommand{\cH}{\mathcal{H}}
\newcommand{\cI}{\mathcal{I}}
\newcommand{\cJ}{\mathcal{J}}
\newcommand{\cK}{\mathcal{K}}
\newcommand{\cL}{\mathcal{L}}
\newcommand{\cM}{\mathcal{M}}
\newcommand{\cN}{\mathcal{N}}
\newcommand{\cO}{\mathcal{O}}
\newcommand{\cP}{\mathcal{P}}
\newcommand{\cQ}{\mathcal{Q}}
\newcommand{\cR}{\mathcal{R}}
\newcommand{\cS}{\mathcal{S}}
\newcommand{\cT}{\mathcal{T}}
\newcommand{\cU}{\mathcal{U}}
\newcommand{\cV}{\mathcal{V}}
\newcommand{\cW}{\mathcal{W}}
\newcommand{\cX}{\mathcal{X}}
\newcommand{\cY}{\mathcal{Y}}
\newcommand{\cZ}{\mathcal{Z}}
\newcommand{\maps}\longrightarrow
\newcommand{\cmaps}\Longrightarrow
\newcommand{\vocab}{\tau}
\newcommand{\uest}{\operatorname{{\bf U}}}
\newcommand{\nest}{\operatorname{{\bf N}}}
\newcommand{\mest}{\operatorname{{\bf M}}}
\newcommand{\pest}{\operatorname{{\bf P}}}
\newcommand{\test}{\operatorname{{\bf T}}}
\newcommand{\sest}{\operatorname{{\bf S}}}
\newcommand{\dest}{\operatorname{{\bf D}}}
\newcommand{\cest}{\operatorname{{\bf C}}}
\newcommand{\best}{\operatorname{{\bf B}}}
\newcommand{\aest}{\operatorname{{\bf A}}}
\newcommand{\kest}{\operatorname{{\bf K}}}
\newcommand{\hest}{\operatorname{{\bf H}}}
\newcommand{\gest}{\operatorname{{\bf G}}}
\newcommand{\iest}{\operatorname{{\bf I}}}
\newcommand{\jest}{\operatorname{{\bf J}}}
\newcommand{\eest}{\operatorname{{\bf E}}}
\newcommand{\zest}{\operatorname{{\bf Z}}}

\newcommand{\csp}{\operatorname{CSP}}
\newcommand{\tcsp}{\operatorname{TCSP}}
\newcommand{\tpol}{\operatorname{TPol}}
\newcommand{\ext}{\operatorname{ext}}
\newcommand{\set}[1]{\overline{#1}}
\newcommand{\atomic}{\operatorname{{\mathcal A}}}
\newcommand{\atomicsent}{\operatorname{{\mathcal B}}}
\newcommand{\composed}{\circ}
\newcommand{\atom}{\alpha}
\newcommand{\atomsent}{\beta}
\newcommand{\sent}{\operatorname{sent}}
\newcommand{\type}{\operatorname{type}}
\newcommand{\pr}{\operatorname{pr}}
\newcommand{\ide}{\operatorname{id}}
\newcommand{\testfixed}{\operatorname{{\mathcal TK}}}
\newcommand{\diagram}[1]{{#1}^*}
\newcommand{\sub}{\subseteq}


\newcommand{\arity}{\rho}
\newcommand{\rsymbol}{\operatorname{r}}


\newcommand{\imply}[2]{{\bf (#1)$\rightarrow$(#2)}}
\newcommand{\twoimply}[2]{{\bf (#1)$\leftrightarrow$(#2)}}


\newcommand{\dset}{\operatorname{DS}}
\newcommand{\one}{{\bf 1}}
\newcommand{\origin}{\operatorname{{\mathcal O}}}
\newcommand{\image}{\operatorname{{\mathcal I}}}
\newcommand{\types}{\operatorname{{\mathcal T}}}
\newcommand{\rel}{\operatorname{rel}}
\newcommand{\maj}{\operatorname{MAJ}}

\newcommand{\sat}{\operatorname{SAT}}

\newcommand{\pointnolinear}{K_1}



%\newcommand{\pr}{\operatorname{pr}}
\newcommand{\fin}{\operatorname{fin}}
\newcommand{\var}{\operatorname{var}}
\newcommand{\pvar}{\operatorname{pvar}}
\newcommand{\girth}{\operatorname{girth}}
\newcommand{\comp}{\circ}


\newcommand{\canonic}{\Theta}

\newcommand{\str}{\operatorname{STR}}

\newcommand{\infinitary}{L_{\infty,\omega}}
\newcommand{\infinitarybounded}{L_{\infty,\omega}^\omega}
\newcommand{\pathlogic}{M}
\newcommand{\restpathlogic}{N}
\newcommand{\conjrestpathlogic}{O}


%\input{defpart.tex}
%\input{definitions.tex}

\newcommand{\ba}{\operatorname{{\bf a}}}
\newcommand{\bb}{\operatorname{{\bf b}}}
\newcommand{\bc}{\operatorname{{\bf c}}}
\newcommand{\bd}{\operatorname{{\bf d}}}
\newcommand{\be}{\operatorname{{\bf e}}}
\newcommand{\ideal}{\operatorname{Ideal}}

%\newcommand{\dom}{\operatorname{dom}}
\newcommand{\coCSP}[1]{\mbox{\rm co-CSP$(#1)$}}

\newcommand{\PTIME}{\mbox{\bf PTIME}}
\newcommand{\NP}{\mbox{\bf NP}}
\newcommand{\NL}{\mbox{\bf NL}}
\newcommand{\LS}{\mbox{\bf LOGSPACE}}

\newcommand{\algB}{\operatorname{{\mathcal B}}}
\newcommand{\algA}{\operatorname{{\mathcal A}}}
\newcommand{\algR}{\operatorname{{\mathcal R}}}
\newcommand{\algS}{\operatorname{{\mathcal S}}}
\newcommand{\algD}{\operatorname{{\mathcal D}}}
\newcommand{\algC}{\operatorname{{\mathcal C}}}
\newcommand{\algE}{\operatorname{{\mathcal E}}}
\newcommand{\algH}{\operatorname{{\mathcal H}}}

\newcommand{\un}{\underline}
\newcommand{\ov}{\overline}
%\def\ar{\hbox{ar}}
\def\vect#1#2{#1 _1\zdots #1 _{#2}}
\def\zd{,\ldots,}
\let\sse=\subseteq
\let\la=\langle
\def\lla{\langle\langle}
\let\ra=\rangle
\def\rra{\rangle\rangle}
\let\vr=\varrho
\let\sbq=\sqsubseteq
\let\spq=\sqsupseteq
\let\lra=\longrightarrow
\def\I{{\cal I}}

\newcommand{\Min}{\mbox{\rm Min}}
\newcommand{\Max}{\mbox{\rm Max}}
\newcommand{\Mix}{\mbox{\rm Mix}}
\newcommand{\core}[1]{\mbox{\rm core($#1$)}}

\newcommand{\aB}{\algB}
\newcommand{\aR}{\algR}
\newcommand{\aS}{\algS}
%\newcommand{\pr}{\rm{pr}}
\newcommand{\proj}{\rm{pr}}
\newcommand{\pw}{\rm{pw}} %for path-width

\newcommand{\nested}{\rm nested}


% Now set up environments for theorems, lemmas, etc.
\newtheorem{theorem}{Theorem}[section]
\newenvironment{theo}{\begin{theorem}\rm}{\end{theorem}}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{defi}[theorem]{Definition}
\newtheorem{remark}[theorem]{Remark}
\newenvironment{definition}{\begin{defi}\rm}{\end{defi}}
%\newtheorem{exam}[thm]{Example}
\newtheorem{example}[theorem]{Example}
\newenvironment{ex}{\begin{exam}\rm}{\end{exam}}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{open}[theorem]{Open Problem}
%\newcommand{\proof}{{\sc Proof.\ }}                    % start of proof





%\mainmatter  % start of an individual contribution

% first the title is needed


%% \title{Title\tnoteref{label1}}
%% \tnotetext[label1]{}
%% use optional labels to link authors explicitly to addresses:
%% \author[label1,label2]{<author name>}
%% \address[label1]{<address>}
%% \address[label2]{<address>}



%\author{Catarina Carvalho
 % \and L\'aszl\'o Egri  \and Marcel Jackson  \and Todd Niven \thanks{The first author was supported by grants SFRH/BPD/26216/2006  and  ISFL-1-143 of CAUL financed by FCT and FEDER. The second author was supported by the National Sciences and Engineering Research Council of Canada (NSERC). The third and fourth authors were supported by  ARC Discovery Project DP1094578.}}
%\address{School of Physics, Astronomy and Mathematics, University of Hertfordshire, UK, and Centro de \'Algebra da Universidade de Lisboa, Portugal, \email{ccarvalho@cii.fc.ul.pt }\and School of Computer Science, McGill University,  Canada, \email{legri1@cs.mcgill.ca} \and Department of Engineering and Mathematical Sciences, La Trobe University, Australia,\email{ \{m.g.jackson,t.niven\}@latrobe.edu.au}}%MJ: a nasty hack to get 3,4, sorry.  It saves a line. %CC fixed :-)




 \title{\bf On Maltsev digraphs\footnote{An extended abstract of this paper appeared in the  proceedings of CSR \cite{carvalho2011maltsev}.}}


 \author{Catarina Carvalho\\
 \small School of Physics, Astronomy and Mathematics \\[-0.8ex]
 \small University of Hertfordshire, U.K.\\[-0.8ex]
 \small\tt c.carvalho2@herts.ac.uk\\
\and 
 L\'aszl\'o Egri\thanks{The second author was supported by the National Sciences and Engineering Research Council of Canada (NSERC). }\\
  \small School of Computer Science\\
  \small McGill University, Canada\\[-0.8ex]
\small\tt laszlo.egri@mail.mcgill.ca\\
\and
 Marcel Jackson \qquad Todd Niven\thanks{The third and fourth authors were supported by  ARC Discovery Project DP1094578.}\\
 \small School of Engineering and Mathematical Sciences \\[-0.8ex]
 \small La Trobe University, Australia \\[-0.8ex]
\small\tt\{m.g.jackson, t.niven\}@latrobe.edu.au
}


\date{\dateline{May 31, 2014}{Feb 5, 2015}{Feb 25, 2015}\\
\small Mathematics Subject Classifications: 05C25, 05C60, 05C75, 68E10, 08A70}



% \cortext[cor1]{Corresponding author}
 %\cortext[cor2]{Principal corresponding author}
 
\begin{document}
\maketitle
 
  
 \begin{abstract}   We study digraphs preserved by a Maltsev operation: \emph{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, $\ccL$.  We then
  generalize results from Kazda (2011) %\cite{Kazda:10:Maltsev} 
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 $\ccL$.  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.

\end{abstract}






\section{Introduction}
\label{int}

The study of  relational structures and, in particular,  digraphs preserved by certain operations from universal algebra became extremely important during the last decade. The main driving force behind this is the algebraic constraint satisfaction problem ($\CSP$) dichotomy conjecture, which states that a constraint satisfaction problem $\CSP(\bB)$ is tractable if the relational structure $\bB$ is preserved by a weak-near-unanimity (weak-NU) operation, and is $\ccNP$-complete otherwise \cite{Bulatov/Jeavons/Krokhin:2000:Constraint,Bulatov/Jeavons/Krokhin:2005:Classifying,Maroti/McKenzie:07:Existence}. Generalizing the dichotomy theorem of Hell and Ne\v{s}et\v{r}il \cite{Hell/Nesetril:90:H-Coloring}, the conjecture has been established for digraphs with no sinks and  no sources by showing that the tractable digraphs are very structured, in fact, they retract onto a disjoint union of directed cycles \cite{Barto:2008:Graphs}.
Other results relating the complexity of $\CSP$s on digraphs to the existence of operations that preserve the digraph can be found, for example, in \cite{Barto/et_al:09:CSP,Barto/Bulin:10:CSP}.

Once the tractability of a $\CSP$ is established, one also wishes to know the fine-grained complexity of that $\CSP$, that is,  for which structures $\best$ is $\CSP(\best)$
in some subclass of \ccP, such as  \ccL \ or \ccNL? To establish the membership of a $\CSP$ in a complexity class inside $\ccP$ it is important to study the structure of relational structures (and digraphs) preserved by operations which are more ``restrictive'' than  weak-NU operations, that is, operations that imply the presence of a weak-NU operation. Two important results in this direction, which we will invoke,
are that if a relational structure $\best$ is preserved by a majority operation, then the corresponding $\CSP(\best)$ is in the complexity class $\ccNL$ \cite{Dalmau08:majority}; and if $\CSP(\bB)$ is definable in Datalog and $\bB$ is preserved by a Maltsev operation, then $\CSP(\bB)$ is in $\ccL$ \cite{Dalmau/Larose:2008:Maltsev,Egri:10:Symmetric}.

We study the structure of finite digraphs preserved by a Maltsev operation; we call such graphs \emph{Maltsev digraphs}. We show that Maltsev digraphs retract  either onto the disjoint union of directed cycles or to a directed path. This gives a direct proof that the corresponding $\CSP$ can be expressed with a symmetric Datalog program of width $(2,3)$, and therefore the $\CSP$ is in $\ccL$.\footnote{Membership of these $\CSP$s in symmetric Datalog was independently shown by Kazda~\cite{Kazda:10:Maltsev}. However, his proof is rather indirect, and the width of his symmetric Datalog program is not explicitly stated. Nevertheless, it seems that his approach gives a width guarantee that grows with the size of the target structure: he uses the main result of \cite{Dalmau08:majority}, which gives a width guarantee only for the linear Datalog program that solves the CSP, and then he invokes \cite{Dalmau/Larose:2008:Maltsev} to argue that the CSP is actually in symmetric Datalog. The width in \cite{Dalmau/Larose:2008:Maltsev} also depends on the size of the target. The width of the symmetric Datalog program in the present paper is $(2,3)$.} Kazda \cite{Kazda:10:Maltsev} showed that every Maltsev digraph also admits a majority operation.   Subsequent work by Bulin, Delic, Jackson and Niven \cite{BDJN} showed that there is little opportunity for substantial extension of this result: the possible polymorphism behaviour of digraphs is mostly the same as for general CSPs.  
Nevertheless, we are able to revisit Kazda's argument, and use it to show that Maltsev digraphs also admit a minority polymorphism, and show how for Maltsev digraphs, a range of polymorphism properties are typically determined by the properties of an associated disjoint union of cycles.  
We also extend the results to the conservative setting, showing for example that a conservative Maltsev digraph is preserved by a class of conservative polymorphisms.

Kazda's article \cite{Kazda:10:Maltsev} concludes with an invitation to provide a more direct characterisation of Maltsev digraphs.  We provide this by giving a graph-theoretic characterisation, and providing a $O(|V_G|^4)$ algorithm for recognising Maltsev digraphs.  A similar characterisation is  given for the conservative case; both conditions generalise the rectangularity property of~\cite{Bulatov/Dalmau:06:Simple}.

We apply our results to the list homomorphism problem, $\ccLHOM$, for directed graphs. We show that $\ccLHOM$ for Maltsev digraphs is in \ccL.  The  complexity of 
$\ccLHOM$ for undirected graphs is completely understood \cite{Egri/et_al:2009:Complexity}, and for directed graphs there is a \ccP\ vs. \ccNP\ dichotomy is \cite{Hell/Rafiey:10:Dichotomy}, and a recently announced \ccL\ vs. \ccNL-hard dichotomy \cite{EgriHellLaroseRafiey13}. 

Next we show that a digraph preserved by a Maltsev operation is also preserved by a conservative 2-semilattice operation if and only if the digraph satisfies a certain combinatorial property. We note that if a structure is preserved by a 2-semilattice operation, then $\CSP(\bB)$ is in Datalog and therefore in $\ccP$ \cite{Jeavons/Cohen/Gyssens:1997:Closure}.
We also characterise digraphs (without the assumption of a Maltsev polymorphism) preserved by a conservative 2-semilattice operation
and show that these digraphs can be recognised in \ccNL.

In Section \ref{secdag} we relate directed acyclic graphs (DAGs) preserved by  Maltsev, and conservative Maltsev polymorphisms with series parallel digraphs. We characterize these in the spirit of the existing characterizations of quasi-series parallel and complete bipartite composite digraphs. This characterization allow us to obtain a $O(|V_G|^3)$-time algorithm to recognize if an acyclic digraph is
   Maltsev.
Finally, an inductive construction of directed acyclic graphs preserved by a Maltsev operation is given. The main motivation behind this construction is that we suspect that extending this construction to $n$-permutable digraphs ($2$-permutable digraphs are precisely the Maltsev digraphs \cite{Hagemann/Mitschke:73:n-permutable}) could make progress towards identifying all list homomorphism problems for digraphs  in~$\ccL$. We note that in \cite{Egri/et_al:2009:Complexity}, an inductive construction of conservative $n$-permutable digraphs is key to the identification of all graphs whose $\ccLHOM$ is in $\ccL$.


\section{Preliminaries}

\subsection{Algebra}

We describe the algebraic definitions for digraphs, however, note that these definitions are straightforward to generalize to relational structures.
Let $G=(V_G, E_G)$ and $H=(V_H, E_H)$ be digraphs. A {\em homomorphism} from $G$ to $H$ is a map $f$ from the set of vertices of $G$,
$V_G$, to the set of vertices of $H$, $V_H$, such that for every edge $(u,v) \in E_G$ we have that $(f(u),f(v))$ is an edge in $H$, that is $ (f(u),f(v)) \in E_H$. A digraph $G$ is called a {\em core} if every homomorphism from $G$ to itself is an automorphism, that is,   a permutation on $V_G$. Let $G'$ be a subgraph of $G$. We say that $G$ retracts onto $G'$ if there is a homomorphism $h:G\rightarrow G'$ such that $h$ is the identity map on $G'$. For a finite digraph $H$, we can then define $\CSP(H)$ as the class of all finite digraphs that admit a homomorphism to $H$

An $n$-ary operation on a set $A$ is a function $f:A^n \rightarrow A$. Given a digraph $G$ and an $n$-ary operation $f$ on $V_G$, we say that $f$
\emph{preserves} $G$, or that $f$ is a {\em polymorphism} of $G$,  if for any $n$ edges  $(u_1,v_1),\dots,(u_n, v_n) \in E_G$ (not necessarily
distinct), the pair $(f(u_1,\dots,u_n),f(v_1,\dots,v_n)) \in E_G$.  For an $n$-ary operation $f$, we write $f(x_1,\dots,x_n) \approx f(y_1,\dots,y_n)$ if $f
(x_1,\dots,x_n) = f(y_1,\dots,y_n)$ for all possible values of the $x_i,y_i$,  $i=1, \ldots, r$. A ternary operation $m$ is \emph{Maltsev} if it satisfies $m
(x,x,y) \approx m(y,x,x) \approx y$, \emph{Pixley} if it satisfies $m(x,x,y) \approx m(y,x,x) \approx m(y,x,y) \approx y$, \emph{majority} if it satisfies $m
(x,x,y) \approx m(x,y,x) \approx m(y,x,x) \approx x$, and \emph{minority} if it satisfies $m(x,x,y) \approx m(x,y,x) \approx m(y,x,x) \approx y$. A binary
operation $*$ is \emph{2-semilattice} if it satisfies $x*x\approx x$, $x*y\approx y*x\approx x*(x*y)$.


\subsection{Graph Theory}

Since all graphs in the paper are directed, we use the terms graph and digraph interchangeably.  Throughout, all digraphs are assumed to be finite.  

For a natural number $n$ we write $[n]=\{1, 2,
\ldots, n\}$.
An \emph{oriented path} is a sequence of, not necessarily distinct, vertices $v_1,\dots,v_n$ such that for every $i \in [n - 1]$, either $(v_i, v_{i+1})$
(\emph{a forward edge}) or $(v_{i+1}, v_i)$ (\emph{a backward edge}) is an edge. We use the terms path and oriented path interchangeably. A
\emph{cycle} is an oriented path with starting point $v_1$ and endpoint $v_m$ such that either $(v_m, v_1)$ or $(v_1, v_m)$ is an edge.
The \emph{net length} of a path $P$, $net(P)$, is the number of forward edges minus the number of backward edges in $P$. A \emph{dipath}  (\emph{reverse
dipath}) is a sequence of, not necessarily distinct, vertices $v_1,\dots,v_n$ such that for every $i \in [n - 1]$, $(v_i, v_{i+1})$ ($(v_{i+1}, v_i)$) is an
edge. A \emph{directed cycle} is a dipath $v_1, \ldots, v_n$ such that $(v_n, v_1)$ is also an edge. For a (reverse) dipath $P$, we let $len(P)$ denote the number of edges in $P$. We use the term \emph{simple} dipath or (directed) cycle to indicate that
all vertices of the dipath or (directed) cycle  are distinct.

A \emph{component} of digraph $G$ is a maximal subgraph, $H$, of $G$ such that for every pair of vertices $u,v \in V_H$, there is an oriented path
from $u$ to $v$. A digraph with one component is said to be \emph{connected}. A digraph is  a \emph{directed acyclic graph} (DAG) if it contains no
directed cycles. A DAG $G$ is \emph{layered} if there exists $q \in \bbN$ such that the vertices of $G$ can be partitioned into $q$ levels
$L_0,\dots,L_{q-1}$, such that any edge of $G$ goes from $L_i$ to $L_{i+1}$, for some $i=0,  \ldots, q-2$.



Let $G$ be a digraph, and  $x$  a vertex of $G$. We define  $x^{+1}=\{y \in V_G: (x,y) \in E_G\}$, and  $x^{-1}=\{y \in V_G: (y,x) \in E_G\}$. We call a
vertex $v$ a \emph{source} if $v^{-1} = \varnothing$, and a \emph{sink} if $v^{+1} = \varnothing $. If $u$ and $v$ are vertices of $G$, $u \stackrel{k}
\rightarrow v$
denotes the existence of a dipath from $u$ to $v$ of length $k$; $u \rightarrow v$ denotes $u \stackrel{1} \rightarrow v$.  For each vertex $x$ of $G$ and each $k\ge 1$, we define $x^{+k}=\{y \in V_G:  x \stackrel{k} \rightarrow y\}$,  $x^{-k}=\{y \in V_G:  y \stackrel{k}\rightarrow  x\}$, and $x^{\pm k}=\{y \in V_G:  x \stackrel{k}\rightarrow  y \ {\rm or} \ y \stackrel{k}\rightarrow x \}$.

The $k$th \emph{power} of a graph, $G$, is a graph, $G^k$, with the same set of vertices as $G$  and an edge between two vertices $u, v$ if and only if  $u\stackrel{k}
\rightarrow v$.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Retracts of Maltsev digraphs}\label{retract_section}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{definition}[totally rectangular]
  A digraph $G$ is \emph{$k$-rectangular} if the following implication holds for all vertices $x,y,u,v$:
\[
x\stackrel{k}\rightarrow u\And
y\stackrel{k}\rightarrow u\And y\stackrel{k}\rightarrow v\Rightarrow
x\stackrel{k}\rightarrow v.
\]
A digraph is \emph{rectangular} if it is $1$-rectangular, and  \emph{totally rectangular} if it is $k$-rectangular for
every $k \in \mathbb{N}$.
\end{definition}

It is not hard to verify that a Maltsev digraph must be totally rectangular, and in Section~\ref{rectangular_and_alg}  (see Corollary \ref{cor:main}) we show that indeed the two properties are equivalent.
\begin{example}
 The digraph in Fig.~\ref{2N} is rectangular but not $2$-rectangular. While the digraph in Fig.~\ref{fig:patch} is totally rectangular.
\begin{figure}[ht!]\begin{center}
%\vspace{-0.6cm}
\begin{picture}(60,50)
\put(10,0){\circle*{4}}
\put(10,20){\circle*{4}}
\put(10,40){\circle*{4}}
\put(30,20){\circle*{4}}
\put(50,0){\circle*{4}}
\put(50,20){\circle*{4}}
\put(50,40){\circle*{4}}
\put(10,0){\vector(0,1){18}}
\put(10,20){\vector(0,1){18}}
\put(50,20){\vector(0,1){18}}
\put(50,0){\vector(0,1){18}}
\put(50,0){\vector(-1,1){18}}
\put(30,20){\vector(-1,1){18}}
\end{picture}
\caption{A rectangular digraph that is not $2$-rectangular.}\label{2N}
\end{center}
%\vspace{-0.9cm}
\end{figure}\end{example}

%\vspace{0.2cm}

\begin{figure}[ht!]\begin{center}
\vspace{-0.3cm}
\begin{picture}(60,40)
\put(10,0){\circle*{4}}
%\put(-5,0){$g$}
\put(10,20){\circle*{4}}
%\put(21,18){$c$}
%\put(54,18){$d$}
\put(10,40){\circle*{4}}
%\put(0,18){$a$}
\put(30,20){\circle*{4}}
%\put(-5,38){$e$}
\put(50,20){\circle*{4}}
\put(70,0){\circle*{4}}
%\put(75,18){$b$}
\put(70,20){\circle*{4}}
%\put(75,0){$f$}
\put(70,40){\circle*{4}}
%\put(75,38){$h$}

\put(10,0){\vector(0,1){18}}
\put(10,0){\vector(2,1){38}}
\put(10,20){\vector(0,1){18}}
\put(70,20){\vector(0,1){18}}
\put(70,0){\vector(0,1){18}}
\put(70,0){\vector(-2,1){38}}
\put(30,20){\vector(-1,1){18}}
\put(50,20){\vector(1,1){18}}
\end{picture}
\end{center}
\vspace{-0.3cm}
\caption{A Maltsev digraph with no conservative Maltsev polymorphism.}\label{fig:patch}
\vspace{-0.3cm}
\end{figure}




We now state the main result of this section.
\begin{theorem}\label{retraction_theorem}
  Let $G$ be a totally rectangular digraph. If $G$ is acyclic then $G$
  retracts onto a simple dipath. Otherwise $G$ retracts onto the
  disjoint union of simple directed cycles.
\end{theorem}
The proof of Theorem~\ref{retraction_theorem} is a
direct consequence of Lemma~\ref{retraction_for_connected} below.
We begin with some definitions and simple observations.

\begin{lemma}\label{path_retraction}
Let $G$ be a digraph. Then $G$ is layered if and only if for every pair of vertices $u,v $ in  $G$, and any pair of oriented paths $P$ and $Q$ from $u$ to $v$, it holds that $net(P) = net(Q)$.
\end{lemma}

\begin{definition}
Let $G$ be a digraph that contains a directed cycle. Let $C$ be a shortest directed cycle in $G$ and assume it has length $m$.
We say that $G$ is  \emph{inconsistent} if there exist two vertices $u, v$ in $G$ such that, there are two different oriented paths of net lengths $\ell_1$ and $\ell_2$ from $u$ to $v$ such that $\ell_1 \not \equiv \ell_2 \mod m$. Otherwise we say that $G$ is \emph{consistent}.
\end{definition}

\begin{proposition}\label{cycle_retraction}
Let $G$ be a connected digraph that contains a directed cycle. Let $C$ be a shortest directed cycle in $G$. Then $G$ retracts onto $C$ if and only if $G$ is consistent.
\end{proposition}
\begin{proof}
Assume that  $C$ has length $m$. If $G$ is consistent, then choose an arbitrary vertex of $C$ and label it with $0$. Call this vertex $s$. For each vertex $v \in G \backslash s$, find an oriented path $P$ from $s$ to $v$. Assume $P$ has net length $\ell$. Label $v$ with the number $\ell \mod m$. Since $G$ is consistent, this labeling is well defined. It is easy to see that the mapping that sends every vertex with label $i$ to the vertex of $C$ that has label $i$ is a retraction of $G$ onto $C$.

Conversely, assume that $G$ retracts to $C$ through a homomorphism $h$. Label every vertex $v$ with $h(v)$. It is not difficult to see that for any two vertices $u$ and $v$ of $G$ such that there are two different (not necessarily simple) oriented paths of net lengths $\ell_1$ and $\ell_2$ from $u$ to $v$, it must be that $\ell_1 \equiv \ell_2 \mod m$.
\end{proof}





The following lemma relates total rectangularity with lengths of  paths in a digraph.
\begin{lemma}\label{reduction}
Let $G$ be a totally rectangular digraph and $u,v$ be vertices in  $G$. Let $P$ and $Q$ be two dipaths in $G$  from $u$ to $v$, such that $len(P) > len(Q)$. Set $k = len(P)$, $\ell = len(Q)$, and $d = k - \ell$. Then one of the following two cases occurs:
\begin{enumerate}
\item If $2 \ell > k$, then $G$ contains vertices $u'$, $v'$ and dipaths $P', Q'$ from $u'$ to $v'$ with the following property: $len(P') = \ell$, $len(Q') = 2 \ell - k$, and $len(P') - len(Q') = d$;\label{2l>k}
\item If $2 \ell \leq k$, then $G$ contains a directed cycle of length $d$.\label{2l<=k}
\end{enumerate}
\end{lemma}
\begin{proof}
See Fig.~\ref{Two_cases}. In the first case, let $u'$ be the vertex of $P$ such that the subpath $P_{u'v}$ of $P$ from $u'$ to $v$ has length $\ell$. Let $v'$ be the vertex of $P$ such that the subpath $P_{uv'}$ of $P$ from $u$ to $v'$ has length $\ell$. Applying the $\ell$-rectangularity of $G$ to $P_{u'v}$, $Q$, and $P_{uv'}$, we obtain the desired dipath $P'$ with $len(P') = \ell$. The other required dipath $Q'$ is the subpath of $P$ from $u'$ to $v'$. Since $k = 2\ell - len(Q')$ we have that $len(Q')= 2\ell - k$, and $len(P') - len(Q') = \ell - (2 \ell - k) = k - \ell = d$.

In the second case, the two paths $P'$ and $Q'$ form a cycle of length $\ell + (k - 2 \ell) = d$ because $2 \ell \leq k$.
\begin{figure}[ht!]
\begin{center}
\includegraphics[scale=1]{red-eps-converted-to}
 \caption{Case \ref{2l>k} (left)  and Case \ref{2l<=k} (right) of Lemma~\ref{reduction}.} \label{Two_cases}
\end{center}
%\vspace{-1cm}
\end{figure}
\end{proof}


\begin{definition}
Let $P$ be an oriented path. Let $P_1, \dots, P_n$ be all maximal (with respect to length) directed subpaths of $P$, such that $P_i$ and $P_{i+1}$, $i \in [n-1]$ share a common vertex. We call $P_1, \dots, P_n$ a \emph{directed path decomposition of $P$}. We can obtain a \emph{directed path decomposition for oriented cycles} in a similar way. Note that if an oriented cycle has two maximal directed subpaths, then these two subpaths share two vertices.
\end{definition}


\begin{lemma}\label{oriented->directed}
Let $G$ be a totally rectangular digraph and $u,v \in V_G$. Let $P_1$ and $P_2$ be oriented paths in $G$ from $u$ to $v$. Assume that $net(P_1) > net(P_2)$, and set $d = net(P_1) - net(P_2)$. Then there are vertices $s,t \in V_G$ and dipaths $Q_1$ and $Q_2$ in $G$ from $s$ to $t$, such that $len(Q_1) - len(Q_2) = d$.
\end{lemma}
\begin{proof}
Consider the oriented cycle $C$ formed by $P_1$ and $P_2$. Let $R_0,\dots,R_{n-1}$ be a directed path decomposition of $C$, and assume that $n \geq 2$. Find a shortest segment $R_i$ in the decomposition and assume it has length $k$. See Fig.~\ref{making_shortcut}.
\begin{figure}[ht!]
\begin{center}
\includegraphics[scale=1]{making_shortcut-eps-converted-to}
 \caption{Making a shortcut.}\label{making_shortcut}
\end{center}
\end{figure}
Then both $R_{i-1}$ and $R_{i+1}$ have length at least $k$, where $i-1$ and $i+1$ are considered modulo $n$. Assume without loss of generality that $R_{i-1}$ and $R_i$ have the same endpoint $b$, and $R_i$ and $R_{i+1}$ have the same starting point $c$. Let $a$ be the vertex of $R_{i-1}$ at distance $k$ from $b$ (going backward on $R_{i-1}$), and $d$ be the vertex of $R_{i+1}$ at distance $k$ from $c$. Then using the $k$-rectangularity of $G$, we can make a \emph{shortcut} from $a$ to $d$ to obtain a new oriented cycle $C'$ in $G$. We repeat this procedure until we obtain a cycle which has a directed path decomposition consisting only of two directed paths, $Q_1$ and $Q_2$.

Assume without loss of generality that $Q_1$ is longer than $Q_2$. To see that $net(Q_1) - net(Q_2) = d$, observe that $d$ is the difference of the forward and backward edges in $C$. Applying the above ``shortcutting'' procedure to $C$ to obtain $C'$ does not change the difference of the forward and backward edges in $C$. To see this, observe that we take out $2k$ forward edges and $k$ backward edges from $C$, and then we add back $k$ forward edges to obtain $C'$.
\end{proof}




\begin{lemma}\label{retraction_for_connected}
Let $G$ be a connected totally rectangular digraph. If $G$ is a DAG then $G$ retracts onto a simple dipath. Otherwise $G$ retracts onto a simple directed cycle.
\end{lemma}
\begin{proof}
Assume first that $G$ is a DAG. We claim that $G$ must be layered. Assume, for a contradiction, that $G$ is not layered. By Lemma~\ref{path_retraction}, there exist $u,v \in V_G$ and oriented paths $P$ and $Q$ from $u$ to $v$, such that $net(P) \neq net(Q)$. Using Lemma~\ref{oriented->directed}, we can assume that $P$ and $Q$ are dipaths of different length. Now we repeatedly apply Case~\ref{2l>k} of Lemma~\ref{reduction} as long as it is possible, and then applying Case~\ref{2l<=k} yields a cycle, a contradiction. So $G$ is layered.

Assume that $G$ has levels $L_0,\dots,L_{q-1}$. Fix vertices $s \in L_0$ and $t \in L_{q-1}$, and let $O$ be any oriented path from $s$ to $t$ (such a path exists because $G$ is connected). Applying the total rectangularity of $G$ to appropriate subpaths of $O$, it is easy to see that there exists a dipath $D$ of length $q-1$ from $s$ to $t$ in $G$. Clearly, $G$ retracts onto $D$.

Suppose that $G$ contains a directed cycle. By Proposition~\ref{cycle_retraction}, it is enough to show that $G$ is consistent. Assume this is not the case. Let $C$ be a shortest 
directed cycle in $G$, and assume it has length $m$. Because $G$ is inconsistent, we can find vertices $u,v \in V_G$ and oriented paths $P_1$ and $P_2$ from $u$ to $v$, such 
that $net(P_1) \not \equiv net(P_2) \mod m$. Set $\ell_1 = net(P_1)$ and $\ell_2 = net(P_2)$. Assume w.l.o.g.\ that $\ell_1 > \ell_2$, and that $u$ is a vertex of $C$. Note that if $u
$ is not a vertex of $C$, then we fix a vertex $c$ of $C$ and find any oriented path $S$ from $c$ to $u$. Then attaching $S$ to $P_1$ and $P_2$ at vertex $u$ gives us the 
desired oriented paths. Furthermore, we can assume that $\ell_1 - \ell_2 = d < m$, because if not, we can add $C$-loops from $u$ to $u$ to $P_2$ to increase its length by a 
multiple of $m$, until $\ell_1 - \ell_2 < m$. Using Lemma~\ref{oriented->directed} we obtain directed paths $Q_1$ and $Q_2$ such that $len(Q_1) - len(Q_2) = d$, and then, by 
applying Lemma~\ref{reduction}, we obtain a cycle of length $d$ in $G$, a contradiction.
\end{proof}


By Lemma~\ref{retraction_for_connected}, each connected
component of $G$ retracts either onto a simple dipath or to a
simple directed cycle. The trivial observation that a dipath
homomorphically maps to a cycle completes the proof of
Theorem~\ref{retraction_theorem}.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Characterisations, Polymorphisms and Algorithms}\label{rectangular_and_alg}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Rectangular Characterisations and Other Polymorphisms}
In this section we generalise a technique of Kazda
\cite{Kazda:10:Maltsev} to characterise digraphs that admit Maltsev
and conservative Maltsev polymorphisms as those which are totally
rectangular and universally rectangular respectively and to provide
polynomial time algorithms for recognising the relevant
properties. Furthermore, we show that Maltsev digraphs also admit many
other polymorphisms, and under certain conditions, they also admit
conservative 2-semilattice polymorphisms.


\begin{definition}[conservatively $k$-rectangular, universally
  rectangular]\label{def:univ rect}
  We say that a graph is \emph{conservatively $k$-rectangular} if it
  satisfies the following sentence:
\begin{equation}
\left.\begin{array}{rrrrr}
x\rightarrow &x_1\rightarrow&\dots \rightarrow &x_{k-1}\rightarrow &u\\
y\rightarrow &y_1\rightarrow&\dots \rightarrow &y_{k-1}\rightarrow &u\\
y\rightarrow &z_1\rightarrow&\dots \rightarrow &z_{k-1}\rightarrow &v\\
\end{array}\right\}\Rightarrow \left\{\parbox{5cm}{
There is a path $x\rightarrow w_1 \rightarrow  \dots \rightarrow w_{k-1} \rightarrow v$ with $w_i \in \{x_i,y_i,z_i\}$ for each $i$.
}
\right.\label{eqn:skr}
\end{equation}
A graph that is conservatively $k$-rectangular for all $k\geq 1$ will
be called \emph{universally rectangular}.
\end{definition}
\begin{example}
The digraph in Fig.~\ref{fig:patch} is conservatively $1$-rectangular but not conservatively $2$-rectangular. The digraph in Fig.~\ref{univrect} is universally rectangular.
\begin{figure}[ht!]\begin{center}
\vspace{-0.3cm}
\begin{picture}(60,40)
\put(10,0){\circle*{4}}
%\put(-5,0){$g$}
\put(10,20){\circle*{4}}
%\put(21,18){$c$}
%\put(54,18){$d$}
\put(10,40){\circle*{4}}
%\put(0,18){$a$}
\put(30,20){\circle*{4}}
%\put(-5,38){$e$}
\put(50,20){\circle*{4}}
\put(70,0){\circle*{4}}
%\put(75,18){$b$}
\put(70,20){\circle*{4}}
%\put(75,0){$f$}
\put(70,40){\circle*{4}}
%\put(75,38){$h$}

\put(10,0){\vector(0,1){18}}
\put(10,0){\vector(2,1){38}}
\put(10,0){\vector(1,1){18}}
\put(10,0){\vector(3,1){58}}
\put(10,20){\vector(0,1){18}}
\put(70,20){\vector(0,1){18}}
\put(70,0){\vector(0,1){18}}
\put(70,0){\vector(-2,1){38}}
\put(70,0){\vector(-3,1){58}}
\put(70,0){\vector(-1,1){18}}
\put(30,20){\vector(-1,1){18}}
\put(50,20){\vector(1,1){18}}
\end{picture}
\end{center}
\vspace{-0.3cm}
\caption{A universally rectangular digraph.}\label{univrect}
\vspace{-0.3cm}
\end{figure}
\end{example}



\begin{definition}
Let $G$ be a digraph. Define the binary relation $R^-$ on
$V_G$ by
$x\mathrel{R^-}y$ if $x^{-1}\cap y^{-1}\neq \varnothing$.  The dual relation $R^+$
is defined by
$x\mathrel{R^+}y$ if $x^{+1}\cap y^{+1}\neq \varnothing$.
\end{definition}

In the presence of rectangularity, the relation $R^+$ is an  equivalence relation on the set $\{x\in V_G: x^+\neq \varnothing\}$, the set of vertices of $G$ that are not sinks. Additionally, the relation $R^-$ is an equivalence relation on the set $\{x\in V_G: x^-\neq \varnothing\}$, the set  of vertices of $G$ that are not sources.  So it makes sense to consider the respective factor graphs, this was observed in \cite{Kazda:10:Maltsev}.
We use the notation $G/R^+$ to denote the graph on the $R^+$-classes
of $G$. Given $R^+$-classes $A, B$, we write $A\rightarrow B$ if there
is some $a\in A$ and $b\in B$ with $a\rightarrow b$.  Similarly,
$G/R^-$ denotes the same construction, but using the relation $R^-$.
Note that $G/R^+$ is not strictly an actual graph quotient of $G$,
only a quotient of an induced subgraph of $G$.  Nevertheless, we
sometimes refer to it as ``the quotient of $G$ by $R^+$''.

\begin{lemma}\label{lem:krect}
Let $G$ be a rectangular digraph and $k>1$.
\begin{enumerate}
\item $G$ is $\ell$-rectangular for all $\ell=1,\dots,k$ if and only
  if $G/R^+$ is $\ell$-rectangular for all $\ell=1,\dots,k-1$.
\item If $G$ is conservatively $\ell$-rectangular for all
  $\ell=1,\dots,k$ then $G/R^+$ is conservatively $\ell$-rectangular for all
  $\ell=1,\dots,k-1$.
\end{enumerate}
\end{lemma}
\begin{proof}
  The rectangularity of $G$ ensures that $G/R^+$ is well
  defined.  Consider some $\ell\leq k-1$.  We show that $G$ is
  $(\ell+1)$-rectangular if and only if $G/R^+$ is $\ell$-rectangular.

  Consider vertices $u,v,x,y$ of $G$ such that
  $x/R^+\stackrel{\ell}\rightarrow u/R^+$,
  $y/R^+\stackrel{\ell}\rightarrow u/R^+$ and
  $y/R^+\stackrel{\ell}\rightarrow v/R^+$ in $G/R^+$.  This is
  equivalent to both the following properties holding:
  \begin{enumerate}
  \item[(i)] there are $u_x,u_y\in u/R^+$ and $v_y\in v/R^+$ such that
    $x\stackrel{\ell}\rightarrow u_x$, $y\stackrel{\ell}\rightarrow
    u_x$ and $y\stackrel{\ell}\rightarrow v_y$ in $G$,
  \item[(ii)] there are $u',v'$ with $u\rightarrow u'$ and
    $v\rightarrow v'$ in $G$.
  \end{enumerate}
  Now (i) and (ii) combined are equivalent to
  $x\stackrel{\ell+1}\rightarrow u'$, $y\stackrel{\ell+1}\rightarrow
  u'$ and $y\stackrel{\ell+1}\rightarrow v'$ in $G$, a general
  instance of the premise of $(\ell+1)$-rectangularity of $G$.  If $G$
  is $(\ell+1)$-rectangular then $x\stackrel{\ell+1}\rightarrow v'$
  and as $v_x\mathbin{R^+}v$ we have that
  $x/R^+\stackrel{\ell}\rightarrow v/R^+$ in $G/R^+$ showing that
  $G/R^+$ is $\ell$-rectangular.  Conversely, if $G/R^+$ is
  $\ell$-rectangular then $x/R^+\stackrel{\ell}\rightarrow v/R^+$
  gives $x\stackrel{\ell+1}\rightarrow v'$, showing that $G$ is
  $(\ell+1)$-rectangular.

  To prove the second statement, note that an instance of the premise in 
  Definition~\ref{def:univ rect}~\eqref{eqn:skr} in $G/R^+$ comes from
  an instance of the premise of conservative $(k+1)$-rectangularity in
  $G$. Then the path in $G$ witnessing the conclusion of conservative
  $(k+1)$-rectangularity provides a corresponding path in $G/R^+$
  using the $R^+$-classes of the vertices in the path.
\end{proof}


For a totally rectangular graph $G$, define $G_0=G$ and
$G_{i+1}=G_i/R^+$, $i\ge 1$. From Lemma~\ref{lem:krect} it follows that $G_i$ is defined
for all positive integers $i$, and eventually $G_i$ will either be
empty or a disjoint union of directed cycles (the only situations that $R^+$ can be
trivial). We define
$G_\infty=G_k$, where $k$ is such that $G_k=G_{k+1}$ (that is, $G_\infty$ is
either empty or a disjoint union of directed cycles).


The next lemma is obtained by applying the Maltsev property to the columns of the premise of \eqref{eqn:skr}.

\begin{lemma}\label{lem:malt imples rect}
Let $G$ be a digraph.
\begin{enumerate}
\item If $G$ has a Maltsev polymorphism, then $G$ is totally rectangular.
\item If $G$ has a conservative Maltsev polymorphism, then $G$ is
universally rectangular.
\end{enumerate}
\end{lemma}
\begin{proof}
  We prove the second statement, the first being similar but easier.
  Consider an instance of the premise of $k$-rectangularity in some
  graph $G$ with a conservative Maltsev polymorphism $p$.  As $p$ is a
  polymorphism, applying $p$ to the columns yields a path
  $x=p(x,y,y)\rightarrow p(x_1,y_1,z_1)\rightarrow \dots \rightarrow
  p(x_{k-1},y_{k-1},z_{k-1})\rightarrow p(u,u,v)=v$.  But because $p$
  is conservative we have $p(x_i,y_i,z_i)\in \{x_i,y_i,z_i\}$ so that
  the path witnesses conservative $k$-rectangularity.
\end{proof}




The following lemma is key to the
proof of Theorem~\ref{thm:tot-rect}.
\begin{lemma}\label{lem:patch}
  Let $a,b$ be vertices in a totally rectangular digraph $G$ satisfying conservative
$2$-rectangularity and
  assume that neither $a$ nor $b$ is a source or sink.  If $a/R^+\cap
  b/R^-$ is nonempty then either $b\in a/R^+$ or $a\in b/R^-$.
\end{lemma}
\begin{proof}
  Let $c\in a/R^+\cap b/R^-$.  There are vertices $e,f,g,h$ such that
  $\{a,c\}\subseteq e^{-1}$, $b\in f^{-1}$, $a\in g^{+1}$ and $\{c,b\}\in
  h^{+1}$.  However $G$ is conservatively $2$-rectangular so that there
  is either an edge from at least one of $a,c$ to $f$ or there is an
  edge from $g$ to at least one of $\{b,c\}$.  Then $1$-rectangularity
  shows that either there is an edge from $a$ to $f$
  or from $g$ to $b$.
\end{proof}

To give details of the proof of Theorem \ref{thm:tot-rect}, it is useful to recall the following result, taken directly from \cite{Kazda:10:Maltsev}.

\begin{lemma}\label{lem:kazda}
Let $G$ be a rectangular digraph. Then the following hold:
\begin{enumerate}
\item $R^+$ is an equivalence relation on $G\setminus S^+(G)$, where
  $S^+(G)$ is the set of sinks of $G$.
\item $R^-$ is an equivalence relation on $G\setminus S^-(G)$, where
  $S^-(G)$ is the set of sources of $G$.
\item Whenever $x R^+ y$, we have $x^{+1}=y^{+1}$ and $x^{+1}$ is an
  equivalence class of $R^-$.
\item Whenever $x R^- y$, we have $x^{-1}=y^{-1}$ and $x^{-1}$ is an
  equivalence class of $R^+$.
\item The mapping $\phi:X\mapsto X^{+1}$ is a bijection from the set of
  equivalence classes of $R^+$ to the set of equivalence classes of
  $R^-$ and $\phi$ is an isomorphism from $G/R^+$ to $G/R^-$.
\end{enumerate}
\end{lemma}


We now give a technical lemma, present in \cite{Kazda:10:Maltsev}:
\begin{lemma} \label{lem:polyquotient}
Let $t^+$ be a polymorphism on the graph $G/R^+$, and let $t^-$ be the $n$-ary polymorphism defined by 
\[
t^{-1}(x_1/R^-,\dots,x_n/R^-):=\phi(t^+(\phi^{-1}(x_1/R^-),\dots,\phi^{-1}(x_1/R^-))).
\]
If $t$ is an $n$-ary function on the vertices of $G$ satisfies the following conditions then it is a polymorphism of $G$:
\begin{enumerate}
\item 
 \(
    t^G_i(x_1,\dots,x_n)/R^+=t^+_i(x_1/R^+,\dots,x_n/R^+),
    \)
    when $x_1,\dots,x_n\in G$ are not sinks and 
    \item
    \(
    t^G_i(x_1,\dots,x_n)/R^-=t^-_i(x_1/R^-,\dots,x_n/R^-),
    \)
    when $x_1,\dots,x_n\in G$ are not sources.
    \end{enumerate}
    \end{lemma}
    \begin{proof}
    Note that $t^-$ is a polymorphism by Lemma \ref{lem:kazda} (5).  The proof of the present lemma is given by Kazda~\cite[pp.~394--395]{Kazda:10:Maltsev} in the particular case where $t^+$ is known to be a majority polymorphism, however the proof makes no use of the arity, nor of the majority equations.
    \end{proof}
    
    
    Recall that an equation $s(x_1,\dots,x_n)\approx t(y_1,\dots,y_m)$ function is said to be \emph{balanced} if $\{x_1,\dots,x_n\}=\{y_1,\dots,y_m\}$.  Idempotence is an example of a balanced equation: $s(x,\dots,x)\approx x$.  
\begin{remark}\label{rem:m}
The following theorem makes use of an assumption that a system of term equalities is nontrivial \up(that is, that $x\approx y$ is not a consequence\up).  In general such assumptions are not algorithmically verifiable, but it will be explained in the course of the proof why the particular form used in the assumption can always be satisfied on any set.
\end{remark}


\begin{theorem}\label{thm:tot-rect}
Consider a property $C$ of digraphs defined either by a system of balanced equations, or by the existence of idempotent
polymorphisms $t_1,t_2,\dots,t_k$ \up(not necessarily distinct\up) satisfying a
single equational sequence
\begin{equation}
t_1(x_{1,1},x_{1,2},\dots,x_{1,n_1})\approx \dots \approx
t_k(x_{k,1},x_{n,2},\dots,x_{k,n_k})\approx x,\tag{$*$}\label{eqn:C}
\end{equation}
where $\{x_{1,1},\dots,x_{1,n_1}\}=\dots=\{x_{k,1},\dots,x_{k,n_k}\}$ and $x\in
\{x_{1,1},\dots,x_{1,n_1}\}$.
The following statements are true provided that the equation $x\approx y$ does not
follow from $C$.
\begin{enumerate}
\item Let $G$ be a totally rectangular digraph. Then $G$ has property
  $C$ if and only if $G_\infty$ has property $C$.
\item Let $G$ be universally rectangular. Then $G$ has property $C$
  with each $t_i$ conservative if
  and only if $G_\infty$ has property
  $C$ with each of the $t_i$ conservative.
\end{enumerate}
%The same conclusions can be made without the requirement that $\approx x$ be included in the equational sequence \up(\ref{eqn:C}\up).
\end{theorem}
\begin{proof}
  Our proof is very similar to the main proof in
  \cite{Kazda:10:Maltsev}.  We focus primarily
  on the conservative case (not considered in
  \cite{Kazda:10:Maltsev} which also only explicitly applies to majority equations), as the non-conservative case is obtained
  by following this proof and missing some steps (we give some
  pointers of the required omissions during the proof).  There are two possible kinds of equations mentioned as determining the property $C$ in the theorem statement: systems of balanced equations, and those determined by \eqref{eqn:C}.  In the proof to follow we refer to systems of balanced equations as equations of the first kind, while those of the form in \eqref{eqn:C} (a single family of $k$ of equalities, with $\approx x$) as equations of the second kind.  We mention that in either case, $C$ holds conservatively is the polymorphisms witnessing the defining equations are conservative.
    
  We define a
  notion of \emph{pattern} for $n$-tuples. Let $(x_1,\dots,x_n)$ be an
  $n$-tuple of symbols, in which possibly some repeats occur.  We say
  that an $n$-tuple $(a_1,\dots,a_n)$ \emph{agrees} with the $n$-tuple
  $(x_1,\dots,x_n)$ if $x_i=x_j$ implies $a_i=a_j$.  We will make
  frequent agreement comparisons to the tuples appearing as arguments
  of terms in equations. 

  It is easy to see that if $G$ has conservative property $C$ then so
  does $G/R^+$ by defining
  $t_i(x_1/R^+,\dots,x_n/R^+)=t_i(x_1,\dots,x_n)/R^+$.  Thus, it
  suffices to show that if $G/R^+$ satisfies $C$ conservatively then
  so does $G$.  This will be shown by backward induction over successive
  quotients by $R^+$. This will be verified using Lemma \ref{lem:krect} rather than
  the assumption of the Maltsev property directly, moreover  instead of explicit
  use of universal rectangularity, the argument uses only the fact
  that on each successive quotient by $R^+$, both rectangularity and
  the conclusion of Lemma \ref{lem:patch} hold.

  Assume that
  $G/R^+$ has conservative polymorphisms $t_1^+,\dots,t_k^+$
  witnessing~$C$.  Let $t^{-}_i(x_1,\dots,x_n)$ denote the operation
  given by $\phi t^+_i(\phi^{-1}(x_1),\dots,\phi^{-1}(x_n))$.  We show that
  one can construct conservative functions $t_1^G,\dots,t_k^G$ on
  $G$, each satisfying the conditions stated in Lemma \ref{lem:polyquotient} and such that the equation sequence defining 
  $C$ holds.  By Lemma \ref{lem:polyquotient}, these are the desired family of polymorphisms witnessing $C$ on $G$.

  In the second kind of equation system (those defined by 
  \eqref{eqn:C}), the values of the $t_i$ are forced at many tuples: if
  $(a_1,\dots,a_n)$ agrees with the pattern
  $(x_{i,1},\dots,x_{i,n_i})$ (with $x_{i,p}=x$), then
  $t_i^G(a_1,\dots,a_n)$ must equal $a_p$.  Idempotence may be
  considered as one such case: it forces $t_i(a,\dots,a)=a$.  Note that if some tuple is asked to take two different values under the same term symbol by this process, then this facilitates a proof of $x\approx y$ from \eqref{eqn:C}, which we have assumed does not hold.  Trivially, the reverse implication is true, which justifies the claim in Remark \ref{rem:m}, for term conditions of this second kind.
  Note also that conditions (1) and (2) of Lemma \ref{lem:polyquotient} hold
  trivially for such tuples, because if $(a_1,\dots,a_n)$ agrees with
  the pattern $(x_{i,1},\dots,x_{i,n_i})$, then
  $(a_1/R^+,\dots,a_n/R^+)$ agrees with the pattern
  $(x_{i,1},\dots,x_{i,n_i})$ also, and so on.  We observe that in this second kind of equation \eqref{eqn:C}, the equations defining $C$ are already guaranteed to hold at this point (and what remains is just ensuring they can be extended as polymorphisms to other tuples).

  We now fix some arbitrary linear order $\leq_G$ on the vertices
  $V_G$ and proceed to choose values for $t^G(a_1,\dots,a_n)$ which
  have not so far been forced.  Note that this is where the definition of the
  $t_i^G$ begins in the case of equations of the first kind.
   Assume that one of $a_1,\dots,a_n\in V_G$ is a
  source.  Choose the value of $t^G(a_1,\dots,a_n)$ to be the smallest
  element $a_\ell$ (under $\leq_G$) of $\{a_1,\dots,a_n\}$ such that
  $a_\ell/R^+=t^+(a_1/R^+,\dots,a_n/R^+)$.   This implies that Condition (1) of Lemma \ref{lem:polyquotient} is satisfied for
  $t^G$ at the tuple $(a_1,\dots,a_n)$, while (2) is satisfied
  vacuously.  (In the non-conservative case, we would simply take the
  smallest element of the $R^+$-equivalence class
  $t^+(a_1/R^+,\dots,a_n/R^+)$.)  Dual statements hold if one of
  $a_1,\dots,a_n$ is a sink. 
  
  Note that, given
  $a_\ell/R^+$, the choice of element in the class $a_\ell/R^+$ is determined
  only by the set $\{a_1,\dots,a_n\}$ and the fixed order $\leq_G$.  
 Thus any balanced equation will hold at such tuples.  This also justifies the claim in Remark \ref{rem:m} for term conditions of the first kind, as the construction just given can be applied to any set (treated as a graph with no edges, so that all tuples are sources) carrying a linear order, and clearly any set can be given a linear order.

  Now consider the case where none of the $a_1,\dots,a_n$ are sources
  or sinks.  We  will show that the $R^+$-class
  $t^+(a_1/R^+,\dots,a_n/R^+)$ intersects the $R^-$-class
  $t^-(a_1/R^-,\dots,a_n/R^-)$ and that at least one of $a_1,\dots,a_n$ lies in
  this intersection (this is the conservative part); this will be
  chosen as the value of $t^G(a_1,\dots,a_n)$.
  % The first of these claims is proved in an essentially identical
  % way to Kazda's argument.  We concentrate on the second.

  Since $t^+$ and $t^-$ are conservative functions we have
  $t^+(a_1/R^+,\dots,a_n/R^+)=a_l/R^+$ for some $l\leq n$ and
  $t^-(a_1/R^-,\dots,a_n/R^-)=a_{l'}/R^-$ for some $l'\leq n$.  We
  show that $a_l/R^+\cap a_{l'}/R^-\neq\varnothing$.  Because any
  vertex $u\in V_G$ that is neither a source nor sink has $u\in
  u/R^+\cap u/R^-$ it suffices to consider the case where $l\neq l'$.
  

  Now, as
  $a_i/R^+\cap a_i/R^-\neq \varnothing$, for each $i=1,\dots,n$, we
  have
  \[
  \phi(\phi^{-1}(a_i/R^-))\cap a_i/R^+\neq \varnothing,
  \]
  and therefore
  \[
  (\phi^{-1}(a_i/R^-),a_i/R^+)\in E(G/R^+).
  \]
  Thus
  \[
  (t^+(\phi^{-1}(a_1/R^-),\dots,\phi^{-1}(a_n/R^-)),t^+(a_1/R^+,\dots,a_n/R^+))\in
  E(G/R^+),
  \]
  from which it follows that
  \[
  t^-(a_1/R^-,\dots,a_n/R^-)\cap
  t^+(a_1/R^+,\dots,a_n/R^+)=a_l/R^+\cap a_{l'}/R^-\neq \varnothing.
  \]


  As $a_l/R^+\cap a_{l'}/R^-\neq \varnothing$, we may employ Lemma
  \ref{lem:patch} to show that there is $i\leq n$ with $a_i\in
  a_l/R^+\cap a_{l'}/R^-$.  Choose $t^G(a_1,\dots,a_n)$ to be the
  $\leq_G$-earliest amongst the $a_i\in a_l/R^+\cap a_{l'}/R^-$.  It
  is now trivial that properties 1 and 2 hold, which as observed
  already, ensures that the $t_i^G$ are polymorphisms of $G$.  We must
  show that the equations \eqref{eqn:C} hold for this case (or that balanced equations hold).  The case labelled \eqref{eqn:C} (where $\approx x$ is assumed), has been established earlier in the proof, so we are considering here only systems of balanced equations.  Consider an individual instance of a balanced equation $t_i(x_{i,1},\dots,x_{i,n_i})\approx t_j(x_{j,1},\dots,x_{j,n_j})$ in the list, where $\{x_{i,1},\dots,x_{i,n_i}\}=\{x_{j,1},\dots,x_{j,n_j}\}$.  Now, the equations defining $C$ hold at the level of $t_i^+$, $t_j^+$ and  $t_i^-$, $t_j^-$, so that the process just performed for selecting the value of $t_i$ and $t_j$ at a tuple without sources or sinks will always at least be made within the intersection of the same block of $R^+$ and block of $R^-$.  However the particular choice of element \emph{within} this set was made only in terms of the order $\leq$ and the set $\{a_1,\dots,a_n\}$, which is uniform for both $t_i$ and $t_j$.  Thus equality at such tuples is verified.
\end{proof}

Some instances of polymorphisms satisfying the conditions of Theorem
\ref{thm:tot-rect} are majority, Maltsev and Pixley.  In these cases
$G_\infty$ always has the desired polymorphism, giving the following
corollary.


\begin{corollary}\label{cor:main}
Let $G$ be a digraph.
\begin{enumerate}
\item $G$ admits a (conservative) Maltsev polymorphism iff it admits a (conservative) Pixley operation iff it is totally (universally)
  rectangular.
\item If $G$ is totally (universally) rectangular then $G$ admits a (conservative) minority
  polymorphism and a (conservative) majority polymorphism.
\end{enumerate}
\end{corollary}


\begin{remark}\label{DR_Remark} The first part of  Corollary~\ref{cor:main}
   strengthens the result given in  Lemma 4 of \cite{Dyer/Richerby:10:Complexity}, for the case of digraphs.
   The relational clone $\langle \bB \rangle$ of a structure $\bB$ is the set of all relations that can be expressed with primitive positive first-order formulas (that is, only existential quantification, conjunction, and equality is allowed) from~$\bB$.
When we restrict \cite[Lemma 4]{Dyer/Richerby:10:Complexity} to digraphs, it can  be stated as follows: A digraph $G$ is preserved by a Maltsev operation iff every binary relation in $\langle G \rangle$ is rectangular. It is easy to see and well known that every binary relation in $\langle G \rangle$ can be expressed as $B_G(S,a,b) = \{(h(a),h(b)) | \text{$h$ is a homomorphism from $S$ to $G$}\}$ for a structure $S$ with two distinguished vertices $a$ and $b$. Then Corollary~\ref{cor:main}  implies that for a digraph $G$ to be preserved by a Maltsev operation it is enough to require that only those binary relations in $\langle G \rangle$ that can be expressed as $B_G(S,a,b)$, where $S$ is a directed path with initial vertex $a$ and terminal vertex $b$,
are  rectangular.
\end{remark}

%MJ: moved this to a discussion prior to the corollary.
%It seemed to read better and is slightly shorter.
%\begin{proof}
%Lemma~\ref{lem:malt imples rect} gives us half of 1.--4. The
%other direction for each statement follows from
%Theorem~\ref{thm:tot-rect} and the fact that
%$G_\infty$ is a disjoint union of directed cycles (possibly empty cycles), and
%every disjoint union of directed cycles admits a (conservative) Maltsev,
%(conservative) Pixley polymorphism and (conservative) minority.
%\end{proof}

The above corollary yields an algorithm for verifying if a graph has a
Maltsev (or Pixley) polymorphism.  Indeed, the rectangularity of a digraph is
equivalent to the following property of its adjacency matrix: when two
rows (or two columns) share a common $1$ they are identical.
On an $n$-vertex digraph this property may be verified in $O(n^3)$
steps.  A digraph has a Maltsev polymorphism if and only if each (of at most $n$)
successive quotient by $R^+$ is rectangular, with the process stopping
once there are no $R^+$-classes of size more than $1$ (which happens
after at most $n$ quotients).  Overall this takes $O(n^4)$ steps (quadratic in terms of the size
of the adjacency matrix).

Universal rectangularity (equivalently, the existence of a conservative Maltsev
polymorphism) can also be verified in polynomial time by verifying total
rectangularity and conservative $2$-rectangularity at each successive quotient
by~$R^+$.  In fact, the proof of Theorem \ref{thm:tot-rect} is sufficiently
constructive to construct the desired polymorphisms (when they exist): simply work
backwards from their definition of $G_\infty$. % Details are not given.

%We briefly describe how the proof of Theorem~\ref{thm:tot-rect}
%enables a direct polynomial time construction of a conservative Pixley
%polymorphism in a Maltsev digraph, when it has one.  (When the Maltsev
%digraph has no conservative Pixley polymorphism, this process still
%produces a Pixley polymorphism.)
%
%For a totally rectangular digraph $G$ assume that $G_\infty$ is not
%the empty graph. Therefore $G_\infty=G_k$, for some $k$, is a disjoint
%union of directed cycles and one may construct a conservative Pixley
%polymorphism directly on $G_\infty$: as forced by the Pixley term
%properties and as a first projection elsewhere.  Now we use backwards
%induction to construct a (conservative) Pixley polymorphism on
%$G_{i-1}$ when we have a (conservative) Pixley polymorphism on $G_i$
%using the proof of Theorem~\ref{thm:tot-rect}. We
%note that when $G_i$ has a conservative Pixley polymorphism, the proof
%of Theorem~\ref{thm:tot-rect}
%indicates that it can be constructed in polynomial time without
%verifying universal rectangularity (even though Corollary~\ref{cor:main}
%guarantees universal rectangularity in this case).

\subsection{Conservative 2-Semilattice Polymorphisms}
A disjoint union of directed cycles admits a conservative commutative
binary (ccb) polymorphism (which coincide with conservative
2-semilattice operations) if and only if it contains no even cycles.
This provides a case where Theorem \ref{thm:tot-rect} characterises a
proper subclass of conservative Maltsev digraphs.
%TN remark 1 moved to here.
In this section we classify Maltsev digraphs admitting a ccb polymorphism.  A
corollary of the result will be a sort of converse to
Theorem~\ref{thm:tot-rect}: a Maltsev digraph with a ccb polymorphism
is necessarily conservative Maltsev (Proposition \ref{pro:ccbTOcm} below).

Consider any digraph $G$ and let $*$ be any conservative commutative binary
operation on $V_G$.  The operation $*$ has an easy interpretation as a colouring of
the nondiagonal elements of the cartesian square $V_G^2\backslash\{(v,v)\mid v\in
V_G\}$: the pair $(a,b)$ is coloured $L$ if $a*b=a$ and $R$ if $a*b=b$;
commutativity is equivalent to $(a,b)$ having different colour to $(b,a)$.    (The
exclusion of the diagonal elements is only for convenience.)  We now examine the
consequences of $*$ being a ccb polymorphism.

For any digraph $G$ we define a structure---the \emph{ccb graph} of $G$---on the
nondiagonal elements of the cartesian square $V_G^2\backslash\{(v,v)\mid v\in
V_G\}$. The ccb graph is a graph with two kinds of edges:  ``orienting'' edges, which
are directed, and ``straight'' edges which are considered as having no direction.
 \begin{itemize}
\item A (directed) orienting edge is placed from $(a_1,b_1)$ to $(a_2,b_2)$ if there
are parallel edges connecting each of the following pairs in $G$: $a_1$ and $a_2$;
$b_1$ and $b_2$; and $b_1$ and $a_2$ \emph{but not} $a_1$ and $b_2$.  The following
diagram depicts two situations that an orienting edge pointing from $(a_1,b_1)$ to
$(a_2,b_2)$ can arise:
\begin{center}

\begin{picture}(180,30)
\put(0,0){\begin{picture}(30,30)
\put(10,5){\circle*{4}}
\put(40,5){\circle*{4}}
\put(10,25){\circle*{4}}
\put(40,25){\circle*{4}}
\put(10,5){\vector(1,0){28}}
\put(10,25){\vector(1,0){28}}
\put(10,5){\vector(3,2){28}}
\put(0,0){$b_1$}
\put(0,20){$a_1$}
\put(43,0){$b_2$}
\put(43,20){$a_2$}
\end{picture}}

\put(90,0){\begin{picture}(30,30)
\put(10,5){\circle*{4}}
\put(40,5){\circle*{4}}
\put(10,25){\circle*{4}}
\put(40,25){\circle*{4}}
\put(40,5){\vector(-1,0){28}}
\put(40,25){\vector(-1,0){28}}
\put(40,25){\vector(-3,-2){28}}
\put(0,0){$b_1$}
\put(0,20){$a_1$}
\put(43,0){$b_2$}
\put(43,20){$a_2$}
\end{picture}}
\end{picture}
\end{center}
\item An (undirected) straight edge is placed from $(a_1,b_1)$ to $(a_2,b_2)$ if
there are parallel edges connecting the following pairs: $a_1$ and $a_2$; $b_1$ and
$b_2$; but not  $a_1$ and $b_2$ or $a_2$ and $b_1$.
\end{itemize}

A directed path in the
ccb graph is a path of orienting edges and
straight edges, in which each orienting edge is traversed in a forward
direction.  We now adopt the notation $\leadsto$ to denote directed
paths: note that $(a,b)\leadsto (c,d)$ if and only if $(d,c)\leadsto
(b,a)$.
An important observation is: if $(a,b)$ is not connected to $(c,d)$ in
the ccb graph of $G$ then the compatibility of the ccb operation with
the edges of $G$ does not fail at the pairs $(a, b)$ and $(c, d)$.
Thus \emph{the digraph $G$ admits a ccb polymorphism iff the ccb graph of
$G$ can be coloured by $L$ and $R$ such that $L$ and $R$ are preserved across
straight edges, $L$ is preserved forward across orienting edges and $R$ is preserved
backward across orienting edges}.  Expressed in terms of $\leadsto$ this becomes the
following rules.
 \begin{itemize}
\item[(L)] If $(u,v)$ is coloured $L$ and $(u,v)\leadsto (x,y)$ then:
\begin{itemize}
\item[(1)]  $(x,y)$ is coloured $L$.
\item[(2)] $(y,x)$ is coloured $R$.
\end{itemize}
\item[(R)] If $(u,v)$ is coloured $R$ and $(x,y)\leadsto (u,v)$ then:
\begin{itemize}
\item[(1)]  $(x,y)$ is coloured $R$.
\item[(2)]  $(y,x)$ is coloured $L$.
\end{itemize}
\end{itemize}


In order to show that the existence of a colouring of a ccb-graph can be decided in
polynomial time, we next consider a kind of a M\"obius band.  As the following
example illustrates, we may think of a directed path connecting $(a,b)$ to $(b,a)$
in the ccb-graph of $G$ as a kind of M\"obius band of parallel edges in $G$.
\begin{center}
\begin{picture}(280,70)
\put(0,40){
        \begin{picture}(230,30)
        \put(10,5){\circle*{4}}
        \put(40,5){\circle*{4}}
        \put(10,25){\circle*{4}}
        \put(40,25){\circle*{4}}
        \put(10,5){\vector(1,0){28}}
        \put(10,25){\vector(1,0){28}}
        \put(10,5){\vector(3,2){28}}
        \put(0,0){$b$}
        \put(0,20){$a$}

      \put(70,5){\vector(-1,0){28}}
        \put(70,25){\vector(-1,0){28}}
        \put(70,5){\circle*{4}}
        \put(100,5){\circle*{4}}
        \put(70,25){\circle*{4}}
        \put(100,25){\circle*{4}}
        \put(100,5){\vector(-1,0){28}}
        \put(100,25){\vector(-1,0){28}}
       \put(100,25){\vector(-3,-2){28}}
      \put(103,0){$a$}
        \put(103,20){$b$}
        \put(125,12){(M\"obius band in $G$)}
        \end{picture}
}
\put(0,0){
        \begin{picture}(230,10)
        \put(10,10){\circle*{4}}
        \put(40,10){\circle*{4}}
       \put(10,10){\vector(1,0){28}}
        \put(0,0){$(a,b)$}
        \put(20,12){$O$}
        \put(50,12){$S$}
        \put(80,12){$O$}
       \put(40,10){\line(1,0){28}}
      \put(70,10){\circle*{4}}
        \put(100,10){\circle*{4}}
        \put(70,10){\vector(1,0){28}}
        \put(90,0){$(b,a)$}
        \put(125,12){(directed path in the ccb-graph of $G$)}
        \end{picture}
}
\end{picture}
\end{center}

\begin{theorem}\label{thm:ccb}
A digraph $G$ admits a ccb polymorphism $*$ if and only if for every distinct
$a,b\in G$, the ccb-graph of $G$ does not contain a directed path both from $(a,b)$
to $(b,a)$ and from $(b,a)$ to $(a,b)$.  When a ccb polymorphism exists, it can be
constructed in a polynomial number of steps.
\end{theorem}
\begin{proof}
The forward implication is simply the statement that the colouring of the ccb-graph
must colour each pair $(a,b)$ oppositely to its reverse $(b,a)$, and the colouring
rules (L)(1)--(R)(2) must be obeyed.

Now we show the converse: assume that for every $a,b\in G$, the ccb-graph of $G$
does not contain a directed path from $(a,b)$ to $(b,a)$ and from $(b,a)$ to
$(a,b)$.  We construct (in a polynomial number of steps) a successful colouring by
$L$ and $R$, whence a ccb  polymorphism.

{\bf First phase.}  Begin by finding any pairs $(a,b)$ from which there is a
directed path to the reverse pair $(b,a)$ (necessarily it must contain an orienting
edge, as otherwise there is a path from $(b,a)$ to $(a,b)$).  In every case, colour
$(a,b)$ by $R$ and $(b,a)$ by $L$.  By assumption, no pair is coloured two different
colours simultaneously.  It might appear that the colouring rules might force the
colouring of some further elements of $G^2$, but in fact this is not the case as all
potential applications of rules (L)(1)--(R)(2) are between elements already consistently
coloured by this first phase.  For example, say that $(c,d)\leadsto (a,b)$, with
$(a,b)$ coloured $R$ because of $(a,b)\leadsto(b,a)$.  Then, while (R1) would force
$(c,d)$ to be coloured by $R$, we already have $(b,a)\leadsto (c,d)$, giving
$(c,d)\leadsto (a,b)\leadsto (b,a)\leadsto (d,c)$.  Hence $(c,d)$ was already
coloured by $R$.  (The other cases are equivalent, up to reversing.)

{\bf Second phase.} Now there may  still be some uncoloured pairs.
 We are going to complete the colouring according to the following process which is
to be repeated until all pairs are coloured (we show the process is well defined
below):
take any uncoloured pair, $(a,b)$ say, and colour it arbitrarily; colour any other
pairs for which rules (L)(1)--(R)(2) apply starting from $(a,b)$.

We need to ensure that the second step is well defined, that is, that no pair
$(c,d)$ is forced to have been coloured two different colours simultaneously.  Up to
reversing everything, we can assume without loss of generality that at some stage a
hitherto uncoloured pair $(a,b)$ is given the colour $L$, and that $(a,b)\leadsto
(c,d)$.  There are two potential problems: $(c,d)$ has already been coloured by $R$
(that is, clashing with a previously assigned colour); or that the choice of
colouring $(a,b)$ by $L$ itself also forces $(c,d)$ to be coloured $R$ (that is,
$(a,b)\leadsto (d,c)$).  In either case, we get a contradiction with the assumption
that $(a,b)$ was uncoloured.  In the first case, rule (R)(1) already forces $(a,b)$ to
be coloured $R$ (either at some earlier iteration of the second phase, or if $(c,d)$ was
coloured at the first phase, then so was $(a,b)$ coloured at the first phase).  In the second case,
$(a,b)\leadsto (d,c)$ implies $(c,d)\leadsto (b,a)$, giving $(a,b)\leadsto
(c,d)\leadsto (b,a)$, showing that $(a,b)$ was coloured in the first phase.

Thus, eventually, the desired colouring (and ccb-polymorphism) is eventually achieved.
\end{proof}


Note that the property in Theorem \ref{thm:ccb} can be verified using
Reachability in the ccb-graph of $G$, so is solvable in nondeterministic logarithmic
space.  Hence deciding if a digraph has a ccb polymorphism is in \ccNL\ too.

\begin{proposition}\label{pro:ccbTOcm}
The following are equivalent for a Maltsev graph $G$:
\begin{enumerate}
\item $G$ has a conservative commutative idempotent binary polymorphism;
\item $G$ has a conservative commutative idempotent binary polymorphism and a
conservative Maltsev polymorphism;
\item $G$ has a conservative Maltsev polymorphism and $G_\infty$ is empty or has no
even length cycles.
\end{enumerate}
\end{proposition}
\begin{proof}
(2)$\Rightarrow$(3)$\Rightarrow$(1) follow from Theorem~\ref{thm:tot-rect}, because
a disjoint union of directed cycles has a ccb iff it has no even length cycles.  For
(1)$\Rightarrow$(2) we use Theorem \ref{thm:ccb} to prove a version of Lemma \ref{lem:patch} with conservative 2-rectangularity replaced by ccb.  Indeed we have:
 \begin{claim}\label{lem:patch2}
  Let $a,b$ be vertices in a totally rectangular digraph $G$ admitting a ccb
  polymorphism and
  assume that neither $a$ nor $b$ is a source or sink.  If there is $c\in a/R^+\cap
  b/R^-$ then either $b\in a/R^+$ or $a\in b/R^-$.
\end{claim}
\begin{proof}
The assumptions on $a$ and $b$ lead to the existence of not-necessarily distinct
points $a$, $b$, $c$, $g$, $e$, $f$, $g$ with at least the edges given in
Figure \ref{fig:patch}.  Total rectangularity ensures the existence of $d$.  If
$c=d$ we are done.  Otherwise, as there can be no path of straight edges connecting
$(c,d)$ to $(d,c)$ in the ccb graph of $G$, there must be an edge between one of the
following: $\{a,c\}$ to $h$; $\{b,d\}$ to $e$; $g$ to $\{c,b\}$; or $h$ to
$\{a,d\}$.  But then rectangularity forces either all edges from $\{a,b,c,d\}$ and
$\{e,h\}$ or all edges from $\{g,f\}$ to $\{a,b,c,d\}$.
\end{proof}
It then follows, like in the proof of Theorem~\ref{thm:tot-rect}.



\end{proof}

%MJ2: moved the following to the appendix
% It is not hard to use the classification in Theorem \ref{thm:ccb} to prove a
%version of Lemma \ref{lem:patch} where the assumption of conservative
%$2$-rectangularity is replaced by the combination of total rectangularity and a ccb
%polymorphism (the remaining detail to complete the proof of Proposition
%\ref{pro:ccbTOcm}).  The assumptions of Lemma \ref{lem:patch} (aside from
%conservative $2$-rectangularity) provide the elements $\{a,b,c,e,f,g,h\}$, while
%$2$-rectangularity provides the vertex~$d$.  Then to avoid the ccb graph containing
%a path of straight edges from $(c,d)$ to $(d,c)$, a further parallel edge is forced
%in Figure \ref{fig:patch}.  Then applications of rectangularity yield the
%conclusion of the lemma.


Note that the digraph in Fig.~\ref{fig:patch} is easily seen to admit a
conservative majority polymorphism, a Maltsev polymorphism, but no conservative
Maltsev polymorphism.  So conservative majority cannot replace ccb in Proposition
\ref{pro:ccbTOcm}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Maltsev DAGs}\label{secdag}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

In this section all graphs will be acyclic, that is, DAGs. Recall that all DAGs preserved by a Maltsev polymorphism are layered and retract onto a simple dipath, see Theorem~\ref{retraction_theorem}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{A simple inductive construction of Maltsev DAGs}\label{ind_construction_sec}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

In this section we provide a simple inductive characterisation of totally rectangular DAG.
We note that  in  \cite[Corollary 16]{Kazda:10:Maltsev} Kazda gives an
inductive construction of Maltsev digraphs, however, this construction is
not fully satisfying in the sense that it is non-deterministic, that is, it
does not specify how to obtain the desired preimages, and it   is not clear if
it can be made deterministic. The construction described below, that only works for DAGs,  consists of repeated applications of two straightforward steps (and their reverse versions) which clearly specify how to obtain a new Maltsev DAG from an already constructed one by a certain copying process. We need the following definitions.

\begin{definition}[(Reverse) arborescence]
An \emph{(reverse) arborescence} is a directed tree with root $r$ such that every edge points away from (towards) $r$. An (reverse) arborescence is balanced if every (reverse) dipath from the root to a leaf has the same length.
\end{definition}

\begin{definition}[\emph{$\N(r,h)$} and \emph{$\rN(r,h)$}] %[Subgraphs \emph{$\N(r,h)$} and \emph{$\rN(r,h)$} of a digraph]
Let $G$ be a digraph, $r \in V_G$, and $h \in \bbN$. $\N(r,h)$ ($\rN(r,h)$) is defined to be the subgraph of $G$ whose vertices and edges are the vertices and edges of all (reverse) sub-dipaths  of $G$ which have initial vertex $r$ and length $h$. Let $v$ be a vertex of $\N(r,h)$ ($\rN(r,h)$) such that $v \neq r$. Then $v$ is called an \emph{endpoint} of $\N(r,h)$ ($\rN(r,h)$) if there is a (reverse) dipath of length $h$ from $r$ to $v$. Otherwise $v$ is called an \emph{inner vertex} of $\N(r,h)$ ($\rN(r,h)$).
\end{definition}



\begin{definition}[isolated $\N(r,h)$] %[$\N(r,h)$ ($\rN(r,h)$) isolated in a digraph]
Let $G$ be a digraph. Consider $\N(r,h)$ ($\rN(r,h)$) for some $r \in V_G$ and $h \in \bbN$. We say that $\N(r,h)$ ($\rN(r,h)$) is \emph{isolated in $G$} if for every inner vertex $v$ of $\N(r,h)$, both the in-neighborhood and the out-neighborhood of $v$ belong to $\N(r,h)$ ($\rN(r,h)$).
\end{definition}

We are ready to define the construction formally in Fig.~\ref{construction}. This construction can be used, for example, to define a minority operation for a totally rectangular DAG. %Also, a  more restricted version of the construction can be defined, but it becomes  slightly more technical.


\begin{figure}[ht!]
%\vspace{-0.6cm}
\begin{center}
\framebox{\begin{minipage}{0.98\textwidth}
\begin{enumerate}
\item $\cC$ contains dipaths of all possible lengths $n\in \bbN_0$;
        \smallskip
\item $\cC$ is closed under applying the following operations:
\begin{enumerate}
        \smallskip
\item Given a digraph $G$, let $r \in V_G$ and $h \in \bbN$ such that $\N(r,h)$ is an arborescence. Let $\N'$ be a copy of $\N(r,h)$. Join $\N'$ to $G$ by identifying the corresponding endpoints of $\N'$ and $\N(r,h)$. Let the resulting graph be $G'$;\label{new tree branch step}
    \smallskip
\item Given a digraph $G$, let $r \in V_G$ be such that $r$ has exactly one incoming edge $(p,r)$, and $h \in \bbN$ such that $\N(r,h)$ is an isolated arborescence. Let $\N'$ be a copy of $\N(r,h)$ with root $r'$. Join $\N'$ to $C$ by identifying the corresponding endpoints of $\N'$ and $\N(r,h)$, and adding the edge $(p,r')$. Let the resulting graph be $G'$;\label{multiple tree connection step}
        \smallskip%MJ3: added "in the natural way" (from LE).
\item The reverse version of Step~\ref{new tree branch step} (defined in the natural way);\label{reverse_1}
        \smallskip
\item The reverse version of Step~\ref{multiple tree connection step} (defined in the natural way).\label{reverse_2}
\end{enumerate}
        \smallskip
\item $\cM$ is the set of digraphs that can be obtained by taking disjoint unions of digraphs in $\cC$.
\end{enumerate}
\end{minipage}}
\end{center}
\vspace{-0.3cm}
\caption{Inductive construction of the set $\cM$ of totally rectangular DAGs.}\label{construction}
\vspace{-0.3cm}
\end{figure}

\begin{example}
Consider the totally rectangular DAG $G''$ in Fig.~\ref{ex}. To construct it using the method in Fig.~\ref{construction},  we start with the dipath $G$ and first  apply Step 2a to $G$ to obtain $G'$. Next  we apply  Step 2d to $G'$ obtain $G''$. The thick edges indicate the subgraphs $\N(r,2)$ and $\rN(r,2)$, which are the subgraphs to be copied and attached appropriately.
\end{example}

\begin{figure}%{\textwidth}
\begin{center}
\includegraphics[scale=1]{ind_example-eps-converted-to}
\caption{Construction of a totally rectangular DAG.}\label{ex}
\end{center}
\vspace{-0.6cm}
\end{figure}


%%%%%%% remove for final version????
%The proof of Theorem~\ref{ind_const} (below) and a more restricted version of the construction can be found in the Appendix. There, we also how the construction in Fig.~\ref{construction} can be used, for example, to define a minority operation for a totally rectangular DAG\footnote{Note that this already follows from Corollary~\ref{cor:main} (see Appendix).}



Reversing the argument of Lemma~\ref{decomposition_for_dag} reveals that if $G$ is a totally rectangular DAG, then each component of $G$ can be built using the construction in Figure~\ref{construction} in a very structured manner. We make this restricted construction explicit in Figure~\ref{restricted_construction}.

\medskip

\begin{figure}[ht!]
\begin{center}
\framebox{\begin{minipage}{0.97\textwidth}
Construct every component $C$ of $G$ as follows:
\begin{enumerate}
\item Initially, $C$ is a directed path of arbitrary length;
\begin{enumerate}
\item Using Step~\ref{reverse_1} of the construction in Figure~\ref{construction}, build an arborescence $A$.\label{initial_arb}
\item Choose a vertex layer $L_m$ such that each connected component of the subgraph between $L_0$ and $L_m$ is a balanced arborescence (notice that these arborescences must have their endpoints in $L_m$).\label{loop}
\begin{enumerate}
\item Choose an arbitrary $q \geq 0$, and repeat the following $q$ times. Choose a vertex $v \in L_k$, where $0 \leq k < m$. Apply Step~\ref{new tree branch step} of the construction in Figure~\ref{construction} with $\N(v,m-k)$ to obtain a new graph. \label{strict_constr_new_branch}
\item Choose an arbitrary $q \geq 0$, and repeat the following $q$ times. Choose a vertex $v \in L_k$, where $0 < k < m$. Apply Step~\ref{multiple tree connection step} of the construction in Figure~\ref{construction} with $\N(v,m-k)$. \label{stric_constr_multiple_tree}
\item Choose an arbitrary $q \geq 0$, and repeat the following $q$ times. Choose a vertex $v \in L_k$, where $0 < k < m$. Apply Step~\ref{reverse_1} of the construction in Figure~\ref{construction} with $\rN(v,\ell)$, where $1 \leq \ell \leq k$. \label{strict_constr_adding_path}
\end{enumerate}
\item Either go back to Step~\ref{loop}, choose $L_m$ with a larger $m$ than previously and repeat, or finish the construction.
\end{enumerate}
\end{enumerate}
\end{minipage}}
\end{center}
\caption{Strict construction of totally rectangular DAGs.}\label{restricted_construction}
\end{figure}

We observe the following properties of this restricted construction. In Steps~\ref{strict_constr_new_branch} and \ref{stric_constr_multiple_tree}, $\N(v,m-k)$ is always isolated. In Step~\ref{strict_constr_adding_path} $F = \rN(v,\cdot)$ is always a reverse directed path, and every vertex of $F$ has precisely one in-neighbour.



We can now describe the class of totally rectangular DAGs.
\begin{theorem}\label{ind_const}
The class of totally rectangular DAGs is the set of digraphs $\cM$ defined in Fig.~\ref{construction}.
\end{theorem}
\begin{proof}
Let $G=(V_G, E_G)$ be a layered digraph with levels $L_0, L_1, \ldots, L_n$. We define a natural order on the levels of $G$ as follows: $L_0<L_1<\cdots < L_n$. Given $u\in V_G$ we denote by $level(u)$ the level of $G$ that the vertex $u$ belongs to.
The result then  follows from Lemma~\ref{only_rect} and Lemma~\ref{decomposition_for_dag} below.
\end{proof}


Before stating Lemma~\ref{decomposition_for_dag}  we need some auxiliary results.

\begin{lemma}\label{only_rect}
Let $G$ be a digraph built using the construction in Fig.~\ref{construction}. Then $G$ is totally rectangular.
\end{lemma}
\begin{proof}
We show the result assuming that $G$ is connected, and the result follows. We show that applying a construction step to a totally rectangular digraph $G$ yields a totally rectangular digraph $G'$. Since a directed path is totally rectangular, this will prove the lemma.

Consider the case when $G'$ was obtained from $G$ by an application of Step~\ref{new tree branch step} attaching $\N'$ to $G$. Take any $4$ distinct vertices $a,b,c,d$ such that there are directed paths $P_{ab}$ from $a$ to $b$, $P_{cb}$ from $c$ to $b$, and $P_{cd}$ from $c$ to $d$, each of some length $\ell$. We show that there must be a directed path of length $\ell$ from $d$ to $a$. Observe first that the construction has the property that there is no directed path from a vertex of $G$ to a vertex of $\N'$, and vice versa, except for the endpoints of $\N'$ (which are identified with the corresponding vertices of $G$). Let $I$ be the common vertices of $G$ and $\N'$. We consider four cases:
\begin{enumerate}
\item \emph{Vertices $a$ and $c$ are in $G$.} Then $P_{ab}$, $P_{cd}$, and $P_{cb}$ are subpaths of $G$, so the total rectangularity of $G$ provides a directed path of length $\ell$ from $a$ to $d$.
\item \emph{Vertex $a \in G$ and $c \in \N'$.} See Figure~\ref{a_in_G_c_in_N} for an illustration. Note that this is possible only if each path $P_{ab}$, $P_{cd}$, and $P_{cb}$ has a vertex $u,v$ and $w$, respectively, in $I$. Let $P_{cv}$ denote the subpath of $P_{cb}$ from $c$ to $v$, and $P_{vb}$ the subpath of $P_{cb}$ from $v$ to $b$. Similarly define the subpaths $P_{cw}$ and $P_{wd}$ of $P_{cd}$. Observe that by construction, $P_{cv}$ is a copy of a dipath $P_{c'v}$ from a vertex $c'$ to $v$ in $G$. Similarly, $P_{cw}$ is a copy of a dipath $P_{c'w}$ from a vertex $c'$ to $w$ in $G$. We have dipaths $P_{ab}$ from $a$ to $b$, $P_{c'v}P_{vb}$ from $c'$ to $b$, and $P_{c'w}P_{wd}$ from $c'$ to $d$, each of length $\ell$ and fully inside $G$. Therefore we have a dipath of length $\ell$ from $a$ to $d$.
\item \emph{Vertex $c \in G$ and $a \in \N'$.}
\item \emph{Both vertices $a$ and $c$ are in $\N'$.}
\end{enumerate}
\begin{figure}[ht!]
\begin{center}
\includegraphics[scale=1]{a_in_G_c_in_N}
 \caption{Left: Vertex $a \in G$ and $c \in \N'$ in analysis of Step~\ref{new tree branch step}.\, Right: The case when $P_{cb}$ and $P_{cd}$ meet at $p$ in the analysis of Step 2b. }
\label{a_in_G_c_in_N}
\end{center}
\end{figure}
For the last two cases, an analysis fairly similar to the analysis of the second case can be done.

Suppose now that $G'$ was obtained from $G$ by an application of Step~\ref{multiple tree connection step} of the construction. Let $r$, $r'$, $h$, $p$, $\N(r,h)$, and $\N'$ be as in the definition of Step~\ref{multiple tree connection step}. Take any $4$ distinct vertices $a,b,c,d$ such that there are directed paths $P_{ab}$ from $a$ to $b$, $P_{cb}$ from $c$ to $b$, and $P_{cd}$ from $c$ to $d$, each of the same length $\ell$. We show that $d\stackrel{\ell}\rightarrow a$. If $level(a) = level(c) \geq level(r)$, then obviously, the same analysis works as for Step~\ref{new tree branch step}. In addition,  $level(b) = level(d) > level(p)$ because otherwise all paths are fully inside $G$ and the total rectangularity of $G$ proves the claim.

Furthermore, there must be two (distinct) edges $e_1$ and $e_2$ among the edges of $P_{ab}$, $P_{cb}$ $P_{cd}$, such that $e_1$ is an edge in $A = \{\N(r,h) \cup (p,r)\}$ and $e_2 \in B = \{\N' \cup (p,r')\}$. To see this, remove $A$ from $G'$ to obtain the graph $G$, and observe that $F$ is isomorphic to $G$. Assume then that there is no edge of $P_{ab}$, $P_{cb}$ $P_{cd}$ in $A$. The total rectangularity of $F$ yields the desired path from $a$ to $d$. Because $\N(r,h)$ and $\N'$ are isolated and $p$ is the only incoming edge of $r$ and $r'$, the only way that at least two of $P_{ab}$, $P_{cb}$ $P_{cd}$ can be in $A$ and $B$ is if at least two of $P_{ab}$, $P_{cb}$ $P_{cd}$ enters $A$ and $B$ through $p$.

If $P_{ab}$ and $P_{cd}$ both meet $p$, then we obviously have a dipath from $a$ to $d$. If $P_{ab}$ and $P_{cb}$ meet at $p$ then let $P_{ap}$ be the subpath of $P_{ab}$ from $a$ to $b$, and $P_{cp}$ the subpath of $P_{cb}$ from $c$ to $p$. Assume $k = len(P_{ap}) (= len(P_{cp}))$, and let $Q$ be the subpath of $P_{cd}$ starting at $c$ and taking the first $k$ edges. Suppose the endpoint of $Q$ is $e$. Then by the total rectangularity of $G$, there is a path of length $k$ from $a$ to $e$. This path from $a$ to $e$ and the subpath of $P_{cd}$ from $e$ to $d$ provides the desired path from $a$ to $d$.

If $P_{cb}$ and $P_{cd}$ meet at $p$, then using the fact that $G$ and $F$ are isomorphic, we can assume w.l.o.g.\ that $P_{cb}$ passes through $r$ and $P_{cd}$ passes through $r'$. Let $P_{r'w}$ be the subpath of $P_{cd}$ from $r'$ to an endpoint $w$. Because $P_{r'w}$ is entirely in $B$, $P_{r'w}$ is a copy of some dipath $Q$ from $r$ to $w$ entirely in $A$ and therefore entirely in $G$. Let $P_{wd}$ the subpath of $P_{cd}$ from $w$ to $d$. Let $P_{eb}$ the subpath of $P_{ab}$ from $e$ to $b$, where $e$ is the vertex of $P_{ab}$ such that $level(e) = level(r)$. Let $P_{rb}$ be the subpath of $P_{cb}$ from $r$ to $b$. Then using the dipaths $P_{eb}, P_{rb}, Q P_{wd}$, we obtain a dipath $R$ from $e$ to $d$ using the total rectangularity of $G$. Then following $P_{ab}$ up to $e$ and then using $R$ we obtain the desired dipath from $a$ to $d$.
\end{proof}

\begin{lemma}\label{main lemma}
Assume that $G$ is a totally rectangular DAG, $r$ is a vertex of $G$, and $h \in \bbN$ such that $A = \N(r,h)$ is an arborescence in $G$. Suppose that $G$ contains a dipath $P = v_0, \dots, v_h$ of length $h$ such that $v_h$ is an endpoint of $A$, but $P$ and $A$ do not share any other vertices. Then $A' = \N(v_0,h)$ is isomorphic to $A$ through an isomorphism $\varphi$, such that $\varphi$ is the identity map on the endpoints of $A'$. Furthermore, $A'$ and $A$ share only the endpoints.
\end{lemma}
\begin{proof}
The proof is by induction on the height $h$ of $A$. When $h=1$ the result trivially follows from the assumption that $G$ is totally rectangular. Assume that $h > 1$. Remove the root $r$ of $A$ to obtain sub-arborescences $A_1,\dots,A_s$, each of height $h-1$, and with roots $r_1,\dots,r_s$, respectively. Fix an arbitrary endpoint $e_i$ for each $A_i$. Once the following Claim is established, it is easy to see that the inductive hypothesis, applied  on paths $Q_1,\dots,Q_n$, yields the result.

\smallskip

\noindent \textbf{\emph{Claim:}} There are dipaths $Q_1,\dots,Q_s$ of length $h$ from $v_0$ to $e_i$, for each $i \in [s]$, such that the only vertex any pair of these paths share is $v_0$. Furthermore for any $i \in [s]$, $Q_i$ does not contain any inner vertices of $A$.

If $s=1$, that is, $r$ has only one out-neighbour, then the claim obviously follows. So assume that $s \geq 2$, and fix a dipath $Q_i$ from $v_0$ to $e_i$ for each $i \in [s]$ as follows. Let $Q$ be a path from $r$ to $e_i$. By assumption $v_h$ is an endpoint of $A$, so there is a path $Q'$ from $r$ to $v_h$. By the total rectangularity of $G$, there must be a path of length $h$ from $v_0$ to $e_i$. Let this path be $Q_i$.

Assume, for a contradiction, that there is pair of paths $Q_i$ and $Q_j$ that share the vertex $x$, and $x \neq v_0$. Suppose that $x$ is as far as possible from $v_0$ (note that if the distance  from $v_0$ to $x$ is different on $Q_i$ and $Q_j$, then $G$ cannot be layered). Let $Q_{i,x}$ and $Q_{j,x}$ be the subpath of $Q_i$ and $Q_j$ from $x$ to $e_i$ and $e_j$, respectively. Suppose that $len(Q_{i,x}) = len(Q_{j,x}) = \ell$. Let $R$ be the reverse directed path of length $\ell$ in $S_i$ starting at $e_i$ and ending at some vertex $t$. Then $Q_{i,x}$, $Q_{j,x}$ and $R$ together with the total rectangularity of $G$ guarantee the existence of a path of length $\ell$ from $t$ to $e_j$. This provides two distinct dipaths of length $h$ from $r$ to $e_j$, contradicting the fact that $A$ is an arborescence.

Suppose, for a contradiction, that for some $i \in [s]$, $Q_i$ contains an inner vertex $f$ of $A$. Let $Q_{i,f}$ be the subpath of $Q_i$ from $v_0$ to $f$, and set $k = len(Q_{i,f})$. Let $P_{rf}$ be a dipath from $r$ to $f$ of length $k$. Then by the rectangularity of $G$, the existence of the paths $Q_{i,f}$, $P_{rf}$ and $v_0,\dots,v_k$ guarantees the existence of a path of length $k$ from $r$ to $v_k$, and therefore $v_k$ is an inner vertex of $A$, a contradiction.
\end{proof}

The following proposition is an easy observation.
\begin{proposition}\label{when N(r,h) is an arborescence}
Let $G$ be a digraph, $r$ a vertex of $G$, and $h \in \bbN$. Then $\N(r,h)$ is an arborescence if, and only if for every pair of distinct vertices $v$, $u$ in $\N(r,h)$, there is at most one dipath from $v$ to $u$.
\end{proposition}

\begin{lemma}\label{make N(r,h) into arborescence}
Let $G$ be a totally rectangular DAG. Let $r$ be a vertex of $G$ and $h \in \bbN$. Assume that $\N(r,h)$ is isolated in $G$. Then $\N(r,h)$ is either an arborescence, or it can be obtained from an arborescence by repeated applications of Step~\ref{multiple tree connection step} of the construction.
\end{lemma}
\begin{proof}
If $\N(r,h)$ is an arborescence there is nothing to do. If $\N(r,h)$ is not an arborescence, then by Proposition~\ref{when N(r,h) is an arborescence}, there is at least one pair of vertices $u$,$v$ such that there are at least two distinct dipaths from $u$ to $v$. It is sufficient to show that in this scenario, we can produce a totally rectangular subgraph $G_s$ of $G$ in which there are fewer directed paths from $u$ to $v$, and an application of Step~\ref{multiple tree connection step} of the construction yields $G$ from $G_s$.

Take the largest $g= 1, \ldots,  h$ such that $\N(r,g)$ is still an arborescence (note that $\N(r,1)$ is always an arborescence). Then we can find an endpoint $v$ of $\N(r,g+1)$ and a vertex $u$ in $\N(r,g)$ (a subgraph of $\N(r,g+1)$) such that there are two disjoint dipaths from $u$ to $v$. Choose such a pair of vertices $u$ and $v$ such that these two distinct dipaths $P = u,w_1,\dots,w_m,v$ and $Q = u,w_1',\dots,w_m',v$ are shortest possible.

By the choice of $u$ and $v$, there is no vertex pair $u'$, $v'$ in $\N(w_1,m)$ such that there is more than one dipath from $u'$ to $v'$. Therefore $\N(w_1,m)$ is an arborescence. To see that $\N(w_1,m)$ is in fact an isolated arborescence, assume for contradiction that there is an edge $(s,t)$ such that $t$ is an inner vertex of $\N(w_1,m)$ and $s \not \in \N(w_1,m)$. Then $t$ is also an inner vertex of $\N(r,h)$, and because $\N(r,h)$ is isolated, $s$ must be in $\N(r,h)$. This implies that $\N(r,h)$ contains some vertex $s'$ such that there are at least two directed paths from $s'$ to $t$. By Proposition~\ref{when N(r,h) is an arborescence}, this would contradict the choice of $g$ because $\N(r,g)$ is an arborescence. Similarly, $\N(w_1',m)$ is an isolated arborescence in $G$. By a similar argument, $w_1$ or $w_2$ has only the in-neighbour $u$.

Using the subpath $w_1',\dots,w_m',v$ of $Q$ and Lemma~\ref{main lemma}, we obtain that $\N(w_1', m)$ is isomorphic to $\N(w_1,m)$. Let $G_s$ be the graph obtained from $G$ be removing $\N(w_1', m)$ (but not the endpoints) and the edge $(u, w_1')$ (but not $u$). It is clear now that we can use Step~\ref{multiple tree connection step} of the construction to obtain $G$ from $G_s$.

To complete the proof, we argue that $G_s$ is totally rectangular. Assume that there are directed paths of length $k$ from $a$ to $c$, $a$ to $d$ and $b$ to $d$ in $G_s$ (and therefore in $G$), but not from $a$ to $d$ in $G_s$. Let the path from $a$ to $d$ in $G$ be $P$. Clearly, some part of $P$ must be removed in $G_s$. If there is a directed path from $a$ to $u$ or $a = u$, and there is a directed path from an endpoint of $\N(w_1', m)$ to $d$ or if $d$ is such an endpoint, then going through $\N(w_1, m)$ instead of $\N(w_1', m)$ gives a path of length $k$ from $a$ to $d$. Suppose therefore that there is no path from $a$ to $u$ and $a \neq u$ (the other case is similar). Since $\N(w_1', m)$ is isolated, and the only in-neighbor of $w_1'$ is $u$, if $a$ is not a vertex of $\N(w_1', m)$ (except for the endpoints), then $P$ does not go through any removed part of the graph, and therefore $P$ is unaffected by the removal. Thus, $a$ is must be a vertex of $\N(w_1', m)$ that is not an endpoint, and therefore $a$ is not in $G_s$, a contradiction.
\end{proof}

\begin{lemma}\label{decomposition_for_dag}
Let $G$ be a totally rectangular DAG. Then each component of $G$ can be built using the construction in Fig.~\ref{construction}.
\end{lemma}
\begin{proof}
Without loss of generality, we assume that $G$ has only one component. By Theorem~\ref{retraction_theorem}, $G$ retracts onto a directed path of some length $n$. We show that if $G$ is not a dipath, then we can always define a totally rectangular DAG (which has one component) such that $G'$ is smaller than $G$ and an application of a step of the construction gives $G$ from $G'$. Let $L_0$ be the bottommost vertex level of $G$ (i.e., the vertex level that contains only sources). $(\star)$ Let $L_i$ be the first level above $L_0$ such that it contains a vertex $w$ which has at least two in-neighbours. Consider the induced subgraph of $G$ between $L_0$ and $L_i$ and call it $H$.

\textit{Case 1:} $H$ contains a sink that is not in $L_i$. Let $t$ be such a sink with the smallest possible level. By the choice of $w$, $t$ has precisely one in-neighbour. Find a shortest reverse directed path $P$ from $t$ to a vertex $c$ such that $c$ has at least two out-neighbours. To see that such a vertex exists, observe that there is an oriented path $Q$ from $t$ to $w$ because $G$ is connected. Since $t$ is a sink, the first edge of $Q$ is a backward edge. As we follow the vertices of $Q$, eventually we must meet a forward edge because $level(t) < level(w)$.

Set $\ell = len(P)$. Since $c$ has at least two out-neighbours, there is a dipath $R$ starting at $c$ and distinct from $P$. We can choose $R$ with length $\ell$ because $t$ is a sink closest to $L_0$. Every vertex of $R$ must have in-degree one by the choice of $w$. Furthermore, $P$ and $R$ shares only the vertex $c$ because otherwise the choice of $w$ would be violated. Let the endpoint of $R$ be $t'$. Remove $P$ from $G$ to obtain $G'$. Then clearly, $G'$ is connected, totally rectangular, and we can obtain $G$ back from $G'$ by applying Step~\ref{reverse_1} with $\rN(t',\ell)$. Repeating this argument if necessary, we can assume that $H$ contains no sinks except in $L_i$.

\textit{Case 2:} $H$ contains no sinks except in $L_i$. Suppose that there is a source $s$ in $H$ such that $level(s) = L_{i - k}$ and $\N(s,k)$ is not an arborescence. Observe that by the choice of $L_i$, $\N(s,k)$ is isolated, and therefore using Lemma~\ref{make N(r,h) into arborescence}, we can obtain a smaller graph $G'$ such that we can get back $G$ from $G'$ by applying Step~\ref{multiple tree connection step}. Repeating this argument if necessary, we can assume that for any source $s$ of $H$, $\N(s,\cdot)$ is an arborescence. (Also note that we can still assume that $H$ contains no sinks except in $L_i$.)

Therefore if there is a connected component $C$ of $H$ that is not an (balanced) arborescence, then $C$ must have more than one sources. Let $s$ and $s'$ be such sources, and assume WLOG that $level(s) \leq level(s')$. Since $C$ is connected, there is a directed path $P$ of some length $\ell$ from $s'$ to an endpoint $e$ of the arborescence $A_s$ rooted at $s$. Let $r$ be the unique vertex of $A_s$ such that there is a directed path of length $\ell$ from $r$ to $e$. Then if $G'$ is the graph obtained from $G$ by removing $\N(s',\ell)$ (except for the endpoints), then we can get back $G$ from $G'$ by applying Step~\ref{new tree branch step} of the construction with $\N(r,\ell)$ of $G'$. Repeating this argument if necessary, we can assume that any connected component of $H$ is an (balanced) arborescence such that all endpoints are in $L_i$.

If $G$ contains a vertex that has indegree at least $2$, then we jump back to $(\star)$ and repeat the whole argument. Notice that when we choose $L_i$, $i$ will increase. If all vertices of $G$ have indegree $1$, then $G$ is an arborescence, and it can be easily constructed starting with a directed path and repeatedly applying Step~\ref{reverse_1}.
\end{proof}


\subsection{Connections with series parallel digraphs}

The class of series parallel digraphs, or series parallel orders, and several modifications of these, such as generalized series parallel (GSP) digraphs, have been widely studied since the 70s. They not only can be used to model series and parallel circuits but also can be applied to scheduling problems, and are interesting from a computational point of view, since several problems that are NP-hard in general, can be solved efficiently when restricted to this class of digraphs. We refer the reader to \cite{Mohring89:tractableordered} for a survey on some computational and structural properties of these digraphs. We will focus on  generalisations of series parallel digraphs, and relate DAGs admitting  Maltsev  and conservative
Maltsev polymorphisms with these classes of graphs. We start with some definitions.

  We say that a digraph $G$ is \emph{$N$-free} if for any four distinct vertices of $G$,  $x,y,u,v$, we have
\[
x\rightarrow u\And
y\rightarrow u\And y\rightarrow v\Rightarrow
x\rightarrow v.
\]

A digraph $G^t $ is said to be a \emph{transitive reduction} of the digraph $G$ if
\begin{enumerate}
\item[(i)] $G^t $ has a directed path from vertex $u$ to vertex $v$ if and only if $G$ has a directed path from vertex $u$ to vertex $v$, and
\item[(ii)]  there is no graph with fewer arcs than $G^t $ satisfying condition (i).
\end{enumerate}



%\underline{ It is shown that the time complexity of the best algorithm for finding the transitive reduction of a graph is the same as the time to compute the transitive closure of a graph or to perform Boolean matrix multiplication.}



%Let $\hest_1$ and $\hest_2$ be any two digraphs: the {\it parallel composition}, $\hest_1+\hest_2$,  of $\hest_1$ and $\hest_2$ is the disjoint union of the digraphs; the {\it series composition}, $\hest_1*\hest_2$, of $\hest_1$ and $\hest_2$ is the digraphs with vertices $H_1\cup H_2$ and edges $(u, v)$ if either $(u, v)$ is an edge in $\hest_1$ or in $\hest_2$ or if $u\in H_1$ and $v\in H_2$.

%The class of {\it series-parallel} digraphs is defined recursively as follows: the one element digraph (with no edges) is series-parallel; $\hest$ is series-parallel if it is obtained by series composition or parallel composition of two smaller series-parallel digraphs.

%\begin{theo}[see where it actually comes from ]
%Given a dag $\hest$, the following are equivalent
%\begin{itemize}
%\item $\hest$ is series-parallel;
%\item Any non-trivial induced subgraph contains  a pair of vertices $u, v$ such that $Prec(u)\backslash \{v\}=Prec(v)\backslash \{u\}$ and $Suc(u)\backslash \{v\}=Suc(v)\backslash \{u\}$;
  %  \item The transitive closure of $\hest$ is rectangular, i.e. it contains no induced $N$.
   % \end{itemize}
   % \end{theo}



%\underline{dags and partial orders}
%A simple algorithm to recognize series-parallel dags runs in $O(n^3)$, where $n$ is the number os vertices of the input dag, see \cite[Algorithm 2.10]{Mohring89:tractableordered}, but faster  algorithms have been obtained to recognize these dags.

%An algorithm that checks in time $O(n+m)$ if a  transitive reduction of directed acyclic digraph (dag) with $n$ vertices and $m$ edges,  is rectangular was given by Syslo \cite{Syslo82:algorithm}.

%A algorithm with the same running time, but where the input can be any dag is given in \cite{Valdes79:seriesparallel}. This algorithm starts by computing the pseudo-transitive reduction of the input dag, checks if this transi  \underline{check this if it actually works for what we want}

%Note it is unlikely that a linear time algorithm exists to calculate the transitive reduction of an arbitrary dag \cite{Aho72:transitive}.



%\underline{relate with GSP}

The class of {\it Minimal Series Parallel (MSP)} is the class of DAGs, defined recursively as follows:
\begin{itemize}
\item the DAG having a single vertex and no edges is MSP;
\item  if $\hest_1=(V_1, E_1)$ and $\hest_2=(V_2, E_2)$ are  MSP, then so are the DAGs obtained from $\hest_1$ and $\hest_2$, by  applying the following operations:
\begin{itemize}
\item {\it parallel composition} $\hest=(V_1\cup V_2, E_1\cup E_2)$, and
\item {\it series composition} $\hest=(V_1\cup V_2, E_1\cup E_2\cup (N_1\times R_2))$, where $N_1$ is the set of sinks of $\hest_1$ and $R_2$ is the set of sources of $\hest_2$.
\end{itemize}
\end{itemize}

A DAG is {\it Generalized Series Parallel (GSP)} if its transitive reduction is MSP.

The class of {\it Quasi-Series-Parallel (QSP)} is the class of DAGs obtained recursively as follows:
\begin{itemize}
\item the DAG having a single vertex and no edges is QSP;
\item if  $\hest_1=(V_1, E_1)$ and $\hest_2=(V_2, E_2)$ are QSP, then so are the DAGs obtained from $\hest_1$ and $\hest_2$, by applying the following operations:
    \begin{itemize}
    \item parallel composition, and
    \item  {\it quasi-series composition}  $\hest=(V_1\cup V_2, E_1\cup E_1\cup (M\times N))$, with $M$ a subset of the set of sinks of $\hest_1$ and $N$ a subset of the set of sources of $\hest_2$.
        \end{itemize}
        \end{itemize}
 Quasi-Series-Parallel graphs have been characterized as follows:


\begin{theo}\cite{Valdes79:seriesparallel}
Given a DAG $\hest=(V, E)$, the following are equivalent:
\begin{enumerate}
\item $\hest$ is QSP;
\item for all $u, v\in V$ either  $u^{-1}=v^{-1}$ or $u^{-1}\cap v^{-1}=\emptyset$;
    \item the transitive closure of $\hest$ contains no induced $N$.
    \end{enumerate}
    \end{theo}
    It is not hard to see that any DAG admitting a Maltsev polymorphism is QSP, but the reverse is not true, indeed the DAG in Figure \ref{2N} is QSP but does not admit a Maltsev polymorphism.% In fact, from this example, we can see that any DAG admitting a Maltsev polymorphism must in fact be equal to its transitive reduction.



A DAG $\hest$ is  {\it complete bipartite composite  (CBC)} if  there exists a set of complete bipartite subgraphs of $\hest$: $B_1, B_2, \ldots, B_k$ called {\it bipartite components} of $\hest$, such that: each edge of $\hest$ belongs to exactly one bipartite component; for every non-sink vertex $v$, all edges leaving $v$ belong to the same bipartite component; for each non-source vertex $v$, all edges entering $v$ belong to the same bipartite component. CBC digraphs admit the following characterization.


\newpage

\begin{theo}\cite{Mohring89:tractableordered}
Given a DAG $\hest=(V, E)$, the following are equivalent:
\begin{enumerate}
\item $\hest$ is CBC;
\item for all $u, v\in V$ either  $u^{\pm1}=v^{\pm1}$ or $u^{\pm1}\cap v^{\pm1}=\emptyset$;
    \item $\hest$ is the transitive reduction of an $N$-free partial order;
    \item $\hest$ is rectangular.
    \end{enumerate}
    \end{theo}

Clearly all Maltsev DAGs are CBC but the reverse is not true, the DAG in Fig.~\ref{2N} is an example of a CBC that is not Maltsev. In fact a characterization in terms of series  parallel constructions for Maltsev DAGs eluded us, even though the characterization of Maltsev DAGs in terms of neighbourhoods is a natural generalization
of the  characterizations given above. Also, we can think of a characterization of Maltsev DAGs in terms of CBC, in the sense that a DAG is Maltsev if and only if  every power of it is CBC, indeed we have:

\begin{theo}Given a DAG $\hest=(V, E)$, the following are equivalent:
\begin{enumerate}
\item $\hest$ admits a Maltsev polymorphism;
\item for every $n\ge 1$, the DAG $\hest^n$ is CBC, that is, $\hest$ is totally rectangular;
\item  $\hest$ is layered and for any  $u, v\in V$ on the same level, we have, for all $k\ge 1$  either $u^{\pm k}=v^{\pm k}$ or $u^{\pm k}\cap v^{\pm k}=\emptyset$;
 \item $\hest$ can be obtained   from a dipath  as described in Fig.~\ref{construction}.
    \end{enumerate}
    \end{theo}
    \begin{proof}
 The fact that $(1)\Leftrightarrow (2)$ was seen in  Lemma~\ref{lem:malt imples rect}, and Theorem~\ref{ind_const}  says that $(1)\Leftrightarrow (4)$. We now show that $(2)\Leftrightarrow (3)$. Assume that $(3)$ holds, and let $x, y, u, v \in V$ be such that there exists $k>0$ such that $x\stackrel{k}\rightarrow u$, $y\stackrel{k}\rightarrow u$ and $y\stackrel{k}\rightarrow v$. It follows that $x^{k}\cap y^k\neq \emptyset$, so we must have $x^k=y^k$. Hence $x\stackrel{k}\rightarrow v$, and so $\hest$ is totally rectangular. 
  Assume now that $\hest$ is totally rectangular. From Theorem~\ref{retraction_theorem} we know that $\hest$ is layered. Let $k>0$ be arbitrary, and $u, v\in V$ be such that $u^k\cap v^k\neq \emptyset$. Let $b\in u^k\cap v^k$, and let $a$ be such that $a\in u^k$. We have $u\stackrel{k}\rightarrow a$, $u\stackrel{k}\rightarrow b$ and $v\stackrel{k}\rightarrow b$. It follows that, since $\hest$ is totally rectangular, $v\stackrel{k}\rightarrow a$, and so $u^k\subseteq v^k$. Similarly we can show that $v^k\subseteq u^k$, and so $u^k=v^k$.  The case when $k<0$ can be dealt with similarly, and we can conclude that $(3)$ holds.
\end{proof}



 \begin{figure} [ht]
\centering
 \includegraphics[angle=270,width=80mm]{exqmsp}
\caption{A DAG that is not Maltsev nor QSP, and a conservative Maltsev DAG that is not MSP.}
\label{pic}
\end{figure}

If we restrict ourselves to DAGs that admit a conservative Maltsev polymorphism, then a simpler characterization of these can be obtained. It is not hard to see that all MSP DAGs admit a conservative Maltsev, but the reverse is not true, the DAG on the right-hand side of Fig.~\ref{pic} admits a conservative Maltsev but is not MSP. In fact, to obtain a characterization of DAGs with conservative Maltsev polymorphism we just need to allow a small generalisation of the construction of MSPs.

%\subsection{The algorithm}

%The idea is to construct complete bipartite components (CBCs), like described in the algorithm in \cite{Valdes79:seriesparallel} (page 8 top left-hand side).
%We construct these components and label them in order, in such a way that it should be possible  to recognize in  $O(k(n+m))$, where $n$ and $m$ are the number of vertices and edges of $\hest$, respectively and $k$ is a constant, if $\hest$ has an $N$ of any size or equivalently is preserved by a Maltsev operation.

%{\bf input:} a dag $\hest$;

%{\bf 1.} Associate a "level" to each vertex, such the arcs always go from level $i$  to level $i+1$. Note that if this is not the case then $\hest$ is not Maltsev, i.e. it has no $N$.

%This can be done by doing a breadth first search (BFS), starting at a root, $r$, labelling it with level $0$, go forward, label all immediate neighbours or $r$  (i.e. vertices $v$ such that $(r, v)$ is an arc f $\hest$) with level $1$ and so on. When reaching  sinks, pick any other vertex $r'$, not labeled yet, find a path up to an already labeled vertex (we label each connected component separately), check the label, say $j$, and retrace your steps labeling the vertices $j-1, \ldots, j-l$,  then proceed from $r'$, that is  labeled $j-l$, label all its immediate neighbours  with $j-l+1$, and so on, in a normal BFS order. Continue until all vertices are labeled.

%If, while labeling the vertices, we find that there is an arc from a vertex labeled $i$ to some vertex with a label different from $i+1$, then STOP.

%This takes less than $O(3(n+m))$ time.

%Note that: From here onwards we will have only dags that retract to a directed path.


%{\bf 2.} Now that all vertices are labeled with a level number, take all the ones on the lowest level (these will be sources),
 %$s_1, \ldots, s_k$,  and put them in a queue $S:=s_1, \ldots, s_k$ (with $s_1$ on top) \underline{I am not 100 per cent sure how long this takes, but once we know} \underline{what the lowest level is we just need to scan all vertices and pick the ones with lowest level I suppose}.

 %Do another BFS, starting at $s_1$ and create "queues" with the neighbours of all the sources in $S$, neighbours at distance 1, $N_1(s_1)$, at distance 2, $N_2(s_1)$, and so on, and then the same for the other elements in $S$. Note that if $x$ is a neighbour of both $s_1$ and $s_2$ at distance 1, then it will be in the set $N_1(s_1)$ but not in $N_1(s_2)$, since we only run BFS once, and this always keeps the same order.

%While doing this, using the edges, create sets $In(v)=\{u : (u, v) \in E(H)\}$, for all $v \in V(H)$, and a queue

%$L_{out}:=$ all edges from $s_1$, all edges from $s_2$, $\ldots$, all edges from $s_k$, all edges from the elements in $N_1(s_1)$ (in the order that they appear here), $\ldots$, all edges from elements in $N_l(s_k)$ (in order).

%Note that these edges are in the order given by the BFS.

%\underline{can this be done efficiently?}

%Then create a queue $L:=s_1, \ldots, s_k, N_1(s_1), \ldots, N_1(s_k), \ldots, N_l(s_1), \ldots, N_l(s_k)$.


%{\bf  3.} We now create the CBCs and label then as we go along.

%CBCs will have different number of labels, depending on their position on the graph. We have seen above that vertices can be associated to a unique level,  so we can think of elements as being on levels $0, 1, \ldots, l$. Components containing elements on levels $0, 1$ will all no bottom right-hand side label, and we say that they are on level $0$, components containing vertices on levels $1, 2$ will contain 1 stage on the bottom right-hand side  label, and we say that they are on level $1$.  Components containing vertices on levels $2$ and $3$ will contain 2 stages  on the label (bottom right-hand side), and we say that they are on level $2$,  and so on.
%We will also  label the components  on the left hand-side with their level number, and on the top right-hand side with their number on the level they belong to.
%Note: components will be complete bipartite digraphs. To the sources of each component $S$ we will call head and denote $h(S)$ and to the sinks of each component we will call tail and denote $t(S)$.


%How it goes:


%\begin{example}
%\includegraphics[angle=270,width=9cm]{exexampleMaltsev}

%On the left-hand side we have the following components

%$_{0}S^{(1)}=\{1, 3\}$, $_{0}S^{(2)}=\{2, 4, 5\}$

%$_{1}S^{(1)}_{1}=\{3, 6\}$, $_{1}S^{(2)}_{2}=\{4, 7\}$, $_{1}S^{(3)}_{2}=\{4, 7\}$

%$_{2}S^{(1)}_{1, 2|1, 2}=\{6, 7, 9\}$, $_{2}S^{(2)}_{2|3}=\{8, 10\}$

%so the algorithm would stop when comparing the second stage label of $_{2}S^{(1)}$ and $_{2}S^{(2)}$, because they intersect and are not equal.


%On the right-hand side the algorithm would not stop, it would finish the labeling and return that the graph has a Maltsev polymorphism. The components (and labels) are

%$_{0}S^{(1)}=\{1, 3, 4\}$, $_{0}S^{(2)}=\{2, 5, 6\}$

%$_{1}S^{(1)}_{1}=\{3, 7\}$, $_{1}S^{(2)}_{1}=\{4, 9\}$, $_{1}S^{(3)}_{2}=\{5, 8\}$, $_{1}S^{(4)}_{2}=\{6, 10\}$

%$_{2}S^{(1)}_{1, 2|1, 3}=\{ 7, 8, 11\}$, $_{2}S^{(2)}_{1, 2|2, 4}=\{9, 10, 12\}$.
%\end{example}

%Start with the first edge in $L_{out}$, $(s_1, v_1)$, and put it in a component $_{0}S^{(1)}$. Put all out-neighbours of $s_1$ in $t(_{0}S^{(1)}1)$ and all in-neighbours of $v_1$ in $h(_{0}S^{(1)}1)$, here they should keep the same order they have in $In(v_1)$, that is given by the BFS.

%Check if the induced subgraph, $_0S^{(1)}$, is  complete bipartite , if not STOP. If yes, then
%\begin{itemize}
%\item remove $s_1$ from $L$ and all edges $(s_1, -)$ from $L_{out}$;
%\item check if $(s_2, v_1)$ is an arc of $\hest$ (note that we  only need to check the arcs in the beginning of $L_{out}$, if yes then remove $s_2$ from $L$ and all arcs $(s_2, - )$ from $L_{out}$ and proceed to $s_3$; if not then we place the first edge of $L_{out}$, $(s_2, v_2)$, on another component $_{0}S^{(2)}$ and continue the process...
%\end{itemize}

%we put all in-neighbors of $v_2$ in $h(_{0}S^{(2)})$ and all out-neighbours of $s_2$ in $t(_{0}S^{(2)})$. We check if the induced subgraph $_{0}S^{(2)}$ is complete, if no STOP; if yes we continue as above.


%After element $s_k$ is removed from $L$ (and all arcs $(s_k, -)$ from $L_{out}$, we have complete bipartite component $_{0}S^{(1)}, _{0}S^{(2)}, \ldots, _{0}S^{(t_0)}$.
%We fix  the first element in the head of each of these component, $_{0}s_1, \ldots,  _{0}s_{t_0}$. Recall that we kept an order (the one given by the BFS) on the elements on the heads of the components.

%We now take the first arc in $L_{out}$, $(n_1, v_1')$,  (recall that $n_1\in N_1(s_1)$)  and put it in a new component $_{1}S^{(1)}$. As before, put all out-neighbours of $n_1$ in  $t(_{1}S^{(1)})$ and all in-neighbours of $v_1'$ in $h(_{1}S^{(1)})$. Check if the induced graph $_{1}S^{(1)}$ is  complete bipartite and if not STOP. If it is complete then we label this component accordingly to the in-neighbours of elements in its head. Since $n_1\in N_1(s_{1})$ we start by setting $_{1}S^{(1)}:= _{1}S_1^{(1)}$, and then
%\begin{itemize}
%\item  for each $x \in h(_{1}S_{1 }^{(1)})$, in order,  look for the elements $_{0}s_1, _{0}s_2, \ldots,  _{0}s_{t_0}$ in  $In(x)$, stop when any of them is found and label  $_{1}S_{1 }^{(1)}$ with the right hand-side label of the corresponding element, i.e. suppose that $_{0}s_3 \in In(x)$ and $_{0}s_4 \in In(y)$, with $x, y \in  h(_{1}S_{1 }^{(1)})$ then $_{1}S_{1 }^{(1)}:=  _{1}S_{1, 3, 4 }^{(1)}$.
%\item next, remove $n_1$ from $L$, and all edges $(n_1, -)$ from $L_{out}$, and look at the next element in $L$, $n_2$. If $(n_2, t)$ is an arc of $\hest$ then remove $n_2$ from $L$ and all arcs $(n_2, -)$ from $L_{out}$, and look at the next element in $L$. Otherwise take the first arc in $L_{out}$ $(n_2, v_2')$, and put it in a new component $_{1}S^{(2)}$. Note that the bottom right hand-side labeling of these components correspond to the components in the previous level, here we  need to check to which component on the previous level  $n_2$ belongs to.  For this, we look in $In(n_2)$ for the elements $_{0}s_1,  _{0}s_2, \ldots,  _{0}s_{t_0}$, and whatever appears first gives the (first) label to the component.
%\end{itemize}


%\underline{I am worried about this label checking because I am not sure how many}

 %\underline{comparisons we are making... basically I just want to go through all edges $(-, n_1)$ again}



 %As we label $_1S^{(2)}$ we compare its label with that of $_1S^{(1)}$, because we want it to be either equal or disjoint. If the first digit of the label of $_1S^{(2)}$ equals the first digit of the label
%of $_1S^{(1)}$ (which is $1$) then, as we label   $_1S^{(2)}$ we compare it component-wise with the label of  $_1S^{(1)}$. If they differ in any component we STOP. If the first digit of the label of  $_1S^{(1)}$ is different from the first digit of the label of  $_1S^{(2)}$, then we create a set of "non-possible choices" $N_1$ with all the elements of the label of  $_1S^{(1)}$. And if any of the elements to label  $_1S^{(2)}$ (and next components on this level) belongs to $N_1$ then we STOP.






%It is worth noting that, by the way BFS works, $_{1}S^{(2)}$ will be labeled $_{1}S_{3 }^{(2)}$ iff the first component on this level is labeled  $_{1}S_{1,2}^{(1)}$.  Also, when labelling $_{1}S^{(3)}$, the first element in the label does not equal the first element of  the label of $_1S^{(2)}$, then the elements of the label of  $_1S^{(2)}$ go in $N_1$. As before, if any element of $N_1$ appears to label  $_1S^{(3)}$ (including the first digit) we STOP.

%Carry on this process until we STOP or all elements from $N_1(s_k)$ are removed from $L$, and the respective edges from $L_{out}$.
%At this stage, if we have not stopped, we have components $_{1}S^{(1)}, _{1}S^{(2)}, \ldots, _{1}S^{(t_1)}$, with diverse labels on the bottom right-hand side, and we fix elements on the head of each component,     $_{1}s_1, \ldots,  _{1}s_{t_1}$.



%We now take the first edge in $L_{out}$, $(m, p)$, and proceed as above, with components $_{2}S^{()}$ . At this stage we will increase the number of "stages" on the bottom right-hand side of the components. The first stage (on the bottom right-hand side) will contain the top right-hand side label of the component, $_{1}S^{()}$,  in the previous level that the elements on the head of this component belong to, and the second stage will contain the bottom right-hand side label of $_{1}S^{()}$. For example suppose that $x, y, z\in h(_{2}S^{(1)})$, and that  $x \in t(_{1}S_{1, 2 }^{(1)} )$, $y \in t(_{1}S_{4, 7}^{(3)})$ and $z\in _{1}S_{6 }^{(5)}$, then $_{2}S^{(1)}:= _{2}S_{1,2, 4, 7, 6| 1, 3, 5 }^{(1)}$.


%We continue, if the algorithm does not stop, to the following level, where there will be 3 stages of labeling on the bottom right-hand side of each component: the top right-hand side label of the components in the previous level that the elements in the head of the component we are labelling belong to, and a copy of the bottom right-hand side labels of the same components (in the same order).


 %As a general first stage label checking for level $i$ we have:

 %We have $_{i}S_{\ldots | \ldots |1, k_1, k_2, \ldots, k_p}^{(1)}$ and want to compare it with the bottom right-hand side label of $_{i}S^{(2)}$. If the first digit (of the first stage of labelling) is $1$
 %then we look in $In(x)$ for all $x\in h(_{i}S^{(2)}$ for the elements $_{i-1}s_{k_{1}}, \ldots,_{i-1}s_{ k_{p}}$, if not all appear we STOP, or if there is an $x$ such that $In(x)$ does not contain one of these elements we also STOP, otherwise we create a set of non-possible choices $N_i:=\{k_1, k_2, \ldots, k_p\}$ and move to $_iS^{(3)}$.
 % We then increase the set $N_i$ as we go along.





 %{\bf Label checking:}


 %Recall that a component on level $i$ will have $i$ stages of labeling on the bottom right-hand side: the labelling referring to level $0$, level $1$, ..., level $i-1$;
%$$_iS^{(p)}_{level \ 0| level  \ 1| \ldots | level \ i-1}$$

%We know that components on level $i-1$ will have equal $i-1$-level labeling if and only if they are consecutive, by the way BFS works, i.e. if we have
%$_{i-1}S^{(p)}_{\ldots|\ldots| 4, 5, 8}$ and $_{i-1}S^{(p+3)}_{\ldots|\ldots| 4, 5, 8}$
%then actually we must have
%$$_{i-1}S^{(p)}_{\ldots|\ldots| 4, 5, 8}, \hspace{0.3cm}  _{i-1}S^{(p+1)}_{\ldots|\ldots| 4, 5, 8}, \hspace{0.3cm}   _{i-1}S^{(p+2)}_{\ldots|\ldots| 4, 5, 8},  \hspace{0.3cm}  _{i-1}S^{(p+3)}_{\ldots|\ldots| 4, 5, 8}$$, and all bottom right-hand side labeling of these components is the same. Note that equal labelling on stage $j$ implies equal labeling on stage $j-1$.

%in this case this might yield labels on level $i$ that are not disjoint nor equal, for example we can have $_{i}S^{(q)}_{\ldots|\ldots|4, 5, 8|p}$ and  $_{i}S^{(q+1)}_{\ldots|\ldots|4, 5, 8|p+1}$ and if we add an extra label to stage $i$ on the second component, say, than these two components will have intersecting but not equal labels on stage $i-1$. We want our algorithm to identify these cases and STOP if such happens.





% We start by checking the labels of components on level $0$, and then move up level by level. We want to make sure that on each level the bottom right-hand side label of  components is either equal or disjoint. And, in fact we only need to check consecutive components \underline{this should be proved separately}

% Assume we are on level $i$.

 %We know already the first stage of labeling of all components on this level is either equal, in which case these components have equal label and they behave as one, or disjoint.



 %We now check the remaining stages,  $2, 3, \ldots, i$,  of labeling.

 %We recall that on the first stage  labels appear in numerical order, due to the order maintained in the sets $In(x)$ and the head of the components. Then on stage $2$ they appear in order related to stage $1$, since they are copies of labels on the previous level, the other stages are similar.

 %We check stage $2$ as follows:  We already know from the labelling process which components have equal labels on all stages, so we do not need to compare these. We scan the first stage of consecutive components (with different labels) for consecutive digits, when we find some we compare the first digit of the respective components on the previous level. If they are equal we compare the labels on stage $2$ component-wise, otherwise we move on. More specifically,
 %%  We know that the first digit of stage $2$ labelling of $_{i}S^{(1)}$ is $1$, if the first digit of stage 1 of  $_{i}S^{(2)}$ is also $1$ then these two components have equal labels at all stages, and we move on to compare $_{i}S^{(2)}$ and $_{i}S^{(3)}$.
 %assume that the  first digit of stage 1 of the label of  $_{i}S^{(2)}$ is not $1$. We check if the first stage of labeling of these two components has any consecutive digits, (we do this by reading the first stage of labeling of $_{i}S^{(1)}$ from left to right, starting at $1$, and carrying on until the digits are not consecutive anymore, then jump to first digit of first stage of $_{i}S^{(2)}$, and so on, so we just read each label once). For the consecutive digits, say $p$ and $p+1$ we compare the first digit of the stage label of $_{i-1}S^{(p)}$ and $_{i-1}S^{(p+1)}$, if it is the same then we compare component-wise stage $2$ labeling of $_{i}S^{(1)}$ and $_{i}S^{(2)}$.
 %If they differ in any component we STOP, otherwise the label of $_{i}S^{(1)}$ and $_{i}S^{(2)}$ is equal from stage $2$ onwards, and we do not need to compare these labels any further. If the first digit of the first stage label of $_{i-1}S^{(p)}$ and $_{i-1}S^{(p+1)}$ is different, we continue scanning the first stage of the labels of $_{i}S^{(1)}$ and $_{i}S^{(2)}$ for consecutive digits, and repeat the process if any are found. We then move on to compare the second stage labels of $_{i}S^{(2)}$ and $_{i}S^{(3)}$, and so on.









%%  For example suppose that we have the following labelling $_{i}S_{\ldots| \ldots |\xi, \xi+1, \eta, \delta} ^{(p)}$ and $_{i}S_{\ldots| \ldots |\xi+2, \gamma,  \delta-1} ^{(p)}$, then we need to compare the first digit of stage 1 of the labelling of $_{i-1}S^{(\xi+1)}$ and  $_{i-1}S^{(\xi+2)}$ (and the same with   $_{i-1}S^{(\delta -1)}$ and  $_{i-1}S^{(\delta)}$). If the first digit is equal then we compare component-wise  the stage $2$ labelling of  $_{i}S^{(p)}$ and  $_{i}S^{(p+1)}$ component-wise, and if they differ at any component we STOP, otherwise we know that these components have equal labelling on stage  $2, \ldots, i$ and we do not need to compare the other stages. If the first digit is different then we compare the first digit of the first stage  of the label of $_{i-1}S^{(\delta -1)}$ and  $_{i-1}S^{(\delta)}$, and so on.

 %%\underline{to do this we just read the first stage of labeling of each component once}


 %To check stages $3$ (and higher), we check on consecutive components for consecutive digits on stage $2$ (and higher, always the one before) and check if  the first digit of the respective components on stage $i-2$ (and lower) is equal, if it is we check stage $3$ (and higher) component-wise, if they differ we STOP, if they are equal we then know that these components have equal label from stage $3$ onwards and do not need to check the other stages.  If the first digits of the first stage labeling of the components $_{i-2}S^{()}$ (and lower levels) is different then we just continue looking for consecutive digits (on consecutive components), as above.

 %If all labels, on all levels,  have been checked and the algorithm has not stopped then $\hest$ is preserved by  a Maltsev  polymorphism.



 %-----------------------------------------------------

% We want each first stage labeling of each component to be either equal or disjoint, i.e.  if $_{i}S^{(p)}:=_{i}S^{(p)}_{\ldots |\ldots |k_1, k_2, k_3}$ and  $_{i}S^{(q)}:=_{i}S^{(q)}_{\ldots| \ldots |k_1, k_2, k_4}$ then we want the algorithm to STOP, the same the labeling at the other stages but this first level can be done as we do the labelling.

 %Start by noting that, by the way BFS works, the first labeling on the bottom right-hand side on the first stage is always the smallest (in the order of the fixed elements of the previous level), since we always pick elements to define this label from  the list $L$.



% We do the following: at each level, say we are on level $i$,  we create a list of non-possible choices, say $_iL_n$,  that works as follows: suppose we have finished labeling $_{i}S^{(p)}_{\ldots | \ldots | k_1, k_2, k_3}$, and that we are labeling $_iS^{(p+1)}$. Also, let $_{i-1} s_{k_1}, _{i-1}s_{k_2}, _{i-1}s_{k_3}$ be the fixed elements from the previous level that yield this label.
%If the edge that defines this component, say $(u, v)$ implies that the first labeling is $k_1$, i.e. $(_{i-1}s_{k_1}, u)$ is an arc of $\hest$, then we check that from all the elements fixed in level $i-1$ only $s_{k_1}, s_{k_2}, s_{k_3}$ are connected to in-neighbours of $v$, if this is not the case we STOP; if the first label of $_iS^{(p+1)}$ is not $s_{k_1}$, then $s_{k_1}, s_{k_2}, s_{k_3}$ are put into $L_n$.

%\underline{next labels cannot use these elements, write this down}

 %................................................



 %As we are labeling in a level there is another thing we need to check: suppose that we have just finished labelling $_{i}S^{(p)}_{k_1, k_2, k_3}$ and that we are labelling  $_{i}S^{(p+1)}$; let $s_{k_1}, s_{k_2}, s_{k_3}$ be the fixed elements from the previous level components; if the first element in the head of  $_{i}S^{(p+1)}$, given by the arc $(u, v)$ say,  is such that $_{i}S^{(p+1)}:= _{i}S^{(p+1)}_{k_1}$ then we check if $s_{k_2}, s_{k_3}$ belong to $In(v)$, if not we STOP and if yes we label  $_{i}S^{(p+1)}:=_{i}S^{(p+1)}_{k_1, k_2, k_3}$ and do not need to check the other elements in the head of this component

%----------------------------------------


%We now assume that the last labelling of bottom right-hand side of any two  components is always either equal or disjoint, so we will need to check that this is also the case for the other stages of labelling.


%So, we want the algorithm to check for the first digit of first labeling in previous level (or corresponding digit on previous stage level, of consecutive labels on the level we are at: for example

%suppose we have
%$$_{i}S^{(1)}_{\ldots| \ldots | 1, 2, 3, 9}, \ \hspace{0.3cm} _{i}S^{(2)}_{\ldots| \ldots | 4, 5, 7}, \ \hspace{0.3cm}  _{i}S^{(3)}_{\ldots| \ldots | 6}, \ \hspace{0.3cm}  _{i}S^{(4)}_{\ldots| \ldots | 8}$$
%then because the labels $3, 4$ belong to different components we need to compare the 1st digit of the last labeling of $_{i-1}S^{(3)}$ and $_{i-1}S^{(4)}$, if it is equal then check, component wise the $i-1$-stage labeling of  $_{i}S^{(1)}$ and  $ _{i}S^{(2)}$, if any of the digits differ STOP, otherwise (and also in the case when the last labeling of $_{i-1}S^{(3)}$ and $_{i-1}S^{(4)}$ where different)  carry on with the digit on $We focus on dags


%\begin{theo}
%Let $\hest$ be a directed acyclic digraph, with levels $0, 1, \ldots, n$. The following are equivalent:
%\begin{enumerate}
%\item $\hest$ admits a Maltsev polymorphism;
%\item for any two vertices $u, v$ of $\hest$, on the same level $l$, we have either $N_{i}(u)=N_i(v)$ or $N_{i}(u)\cap N_i(v)=\emptyset$ for all $i=0, \ldots,  n$, $i\neq l$;
%\item $\hest$ can be constructed in a special way from a directed path of length $n$.
%\item add rectangularity stuff
%\end{enumerate}
%\end{theo}


%The idea now is to have a similar theorem for dags with conservative Maltsev polymorphism. We first define a construction based on the series parallel  construction.
\begin{definition}
The class of  {\it Quasi-Minimal Series Parallel DAGs} (QMSP)
is the class of DAGs obtained recursively as follows:
\begin{itemize}
\item the DAG having a single vertex and no edges is QMSP;
\item if  $\hest_1=(V_1, E_1)$ and $\hest_2=(V_2, E_2)$ and QMSP, then so are the DAGs obtained from $\hest_1$ and $\hest_2$, by applying the following operations:
    \begin{itemize}
    \item parallel composition, and
    \item  {\it End-quasi-series composition}: $\hest=( V_1 \cup V_2, E_1 \cup E_2 \cup (L_1\times F_2))$, where $L_1$ is a subset of the set of sinks on the last level of $\hest_1$, and $F_2$ is a subset of the set of sources on the first level of $\hest_2$.
   \end{itemize}
        \end{itemize}
\end{definition}

We finally give a characterization, similar to the ones presented earlier,  of DAGs admitting a conservative Maltsev polymorphism.

\begin{theo}\label{consmaltsevqmsp}
Let $\hest=(V, E)$ be a DAG. The following are equivalent:
\begin{enumerate}
\item $\hest$ admits a conservative Maltsev polymorphism;
\item $\hest$ is layered, and  for any two vertices $u, v$ of $\hest$, on the same level, we have, for all $i\ge 1$,  either $u^{\pm i}=v^{\pm i}$ or $u^{\pm i}\cap v^{\pm i}=\emptyset$, and
\begin{itemize}
\item[a)] if $u^{+(i-1)}\cap v^{+(i-1)}=\emptyset$ and $u^{+i}=v^{+i}$ then  $(u^{+(i-1)}\cup v^{+(i-1)})\times u^{+i} \subseteq E$, for all $i> 1$,
\item[b)] if $u^{-(j+1)}\cap v^{-(j+1)}=\emptyset$ and $u^{-j}=v^{-j}$ then  $u^{-j} \times (u^{-(j+1)}\cup v^{-(j+1)}) \subseteq E$, for all $j>1$;
\end{itemize}
\item $\hest$ is  QMSP;
\item $\hest$ is universally  rectangular.
\end{enumerate}
\end{theo}

Before proving the theorem, we need the following two lemmas.


\begin{lemma}\label{claimcomplete}
Let $\hest$ be a connected DAG that admits a conservative Maltsev polymorphism. There exists $i\ge 0$ such that all vertices of $\hest$ on  levels $i, i+1$ that are neither sources on level $i+1$, nor sinks on level $i$, form a complete bipartite graph.
\end{lemma}
\begin{proof}
Recall that $\hest$ is layered, and assume that it has levels $0, \ldots, n$.
The proof is by induction on $n$. If $n=0$ then the result trivially holds. %If $n=1$ then $\hest$  has two levels and since it is rectangular we know that it must be a complete bipartite dag.
Assume now that the statement is true for all connected DAGs admitting a conservative Maltsev polymorphism, and  with at most $n-1$ levels. Since $\hest$ is preserved by a conservative Maltsev polymorphism,   the subgraph $\hest'$ induced by the vertices on levels $0, 1, \ldots, n-1$ of $\hest$, also admits a conservative Maltsev polymorphism. If $\hest'$ is connected then the result follows by the inductive hypothesis. So, assume now that $\hest'$ is not connected. Let $\hest_1, \hest_2$ be two connected components of $\hest'$. These components must be connected by an element on level $n$ in $\hest$, since $\hest$ is a connected DAG. Let $a$ be an element of level $n$ of $\hest$ that connects these components. If $\hest$ only has one element on level $n$, then it follows that the vertices of $\hest$ on  levels $n-1$ and $n$  form a complete bipartite DAG, so we assume now that there is at least another element, say $b$, on level $n$ of $\hest$ and, for a contradiction, assume that $a^{-1}\cap b^{-1}=\emptyset$.  We can assume, without loss of generality, that $b$ is connected to $\hest_2$. So we have that there exist distinct elements $v, v'$ belonging to $\hest_2$ and on level $n-1$ of $\hest$ (that is, on the top level of $\hest_2$) such that $(v, a), (v', b)$ are arcs of $\hest$.
Since $\hest_2$ is connected, there exists an element $p$ in $\hest_2$, say on level $k<n-1$ of $\hest$, such that $p\stackrel{n-1-k}\longrightarrow v$ and $p\stackrel{n-1-k}\longrightarrow v'$.
Choose $p$ such that these paths are distinct (that is, $p$ is there only common vertex) and as short as possible. This means that $v, v'$ meet in $p$ and do not meet earlier, and consequently the levels of $\hest_2$ that form the complete bipartite DAG (which we know exist by the inductive hypothesis) appear below level $k$ of $\hest$. If $\hest$ has no elements on level $k$ that belong to the connected component $\hest_1$ then the DAG $\hest_1\cup \hest_2\cup\{a, b\}$ has a complete bipartite induced subgraph on the same levels as $\hest_2$, indeed the same complete bipartite component. If this is the case we just need to deal with other remaining connected components and elements on level $n$ of $\hest$ in the same way, which proves the claim.

So, assume now that $\hest$ has an element on level $k$, say $q$,  that belongs to $\hest_1$, so there  is a vertex $u$ on $\hest_1$ such that $(u, a)$ is an arc of $\hest$ and
$q\stackrel{n-1-k}\longrightarrow u$.
 So we have $q\stackrel{n-k}\longrightarrow a$, $p \stackrel{n-k}\longrightarrow a$ and $p\stackrel{n-k}\longrightarrow b$. Since $\hest$ admits a conservative Maltsev polymorphism there exists a path of length $n-k$ from $q$ to $b$ using only the elements on the paths from $q$ to $a$, $p$ to $a$ and $p$ to $b$. Since $\hest_1$ and $\hest_2$ are disconnected, we must have that this path is all in $\hest_1$ up to level $n-1$ and so $(u, b)$ must be an arc of $\hest$, which contradicts the fact that $a^{-1}\cap b^{-1}=\emptyset$.

Thus it follows that $a^{-1}=b^{-1}$, that is, $a^{-1}\times \{a, b\}$ forms a complete bipartite DAG, on levels $n-1$ and $n$. This can clearly be extended to more connected components of $\hest$ and other elements on level $n$, which proves the claim.
\end{proof}
%This implies that if $\hest$ is a connected dag with more than one level, i.e. different from the graph with one vertex and no edges, then it can be obtained from DAGs $\hest_1, \hest_2$ by means of a quasi-series construction. Clearly, here, the DAG $\hest_1$ is the one containing vertices in levels $0, \ldots, i$ of $\hest$, and $\hest_2$ is the DAG containing all vertices, and edges,  in levels $i+1, \ldots, n$.

\begin{lemma}\label{1implies3} If a DAG $\hest$ admits a conservative Maltsev polymorphism then it is QMSP.
\end{lemma}
\begin{proof}
Let $\hest$ be a DAG, and assume that it has a conservative Maltsev polymorphism. We then know that it retracts to a directed path of some length, say $n+1$, and so we know that the vertices of $\hest$ can be placed into levels $0, 1, \ldots, n$, in such a way that edges are placed between consecutive levels.

We show that $\hest$ can be obtained from  the one vertex and no edges graph, by a sequence of parallel and quasi-series constructions.
Clearly all connected components are joined together by parallel construction, so let $\gest$ be a (maximal) connected component of $\hest$.
By Lemma  \ref{claimcomplete} we know that each connected component of $\hest$ can be obtained by a quasi-series construction from two smaller DAGs, $\hest_1$ and $\hest_2$. Clearly $\hest_1$ and $\hest_2$ are DAGs that admit a conservative Maltsev polymorphism, since they are induced subgraphs of $\hest$. So, we can now look at the connected components of each of these graphs, and repeat the process. We can then conclude that $\hest$ can be obtained by means of parallel and quasi-series constructions from the DAG with a single vertex.
\end{proof}


%\begin{lemma}
%If a dag  is MQSP then it admits a conservative Maltsev polymorphism.
%\end{lemma}

\begin{proof}[Proof of Theorem \ref{consmaltsevqmsp}]


In Lemma \ref{1implies3},  we have  seen that $(1) \Rightarrow (3)$. We now prove that $(3)\Rightarrow (2)$.
Assume that $\hest$ is  QMSP. We show by induction on the number of steps of the quasi-series parallel construction of $\hest$, that condition $(2)$ is satisfied. The base case trivially holds, and parallel constructions do not interfere with neighbourhoods. It is also easy to see that quasi-series construction also preserves condition $(2)$.

Finally, assume that condition $(2)$ holds, and let us see that this implies $(1)$, that is, that $\hest$ (satisfying $(2)$) admits a conservative Maltsev polymorphism. From condition $2 \ a)$ it follows immediately that $\hest$ admits a Maltsev polymorphism, that is, it is totally rectangular. We now show that $\hest$ is universally rectangular.
Suppose this is not the case, then we have distinct paths $x\rightarrow x_1\rightarrow \cdots \rightarrow x_{k-1}\rightarrow u$, $y\rightarrow y_1\rightarrow \cdots \rightarrow y_{k-1}\rightarrow u$ and $y\rightarrow z_1\rightarrow \cdots \rightarrow z_{k-1}\rightarrow v$, and a path $x\rightarrow w_1\rightarrow \cdots \rightarrow w_{k-1}\rightarrow v$, and at least one of the $w_i's$ is different from $x_i ,y_i, z_i$. We can assume, without loss of generality, that this happens with $w_1$, and that $x_1, y_1, z_1$ are all different.  We have $u^{-k}=v^{-k}$, and $u^{-k+1}\cap v^{-k+1}=\emptyset$, since $x_{1}\in u^{-k+1}$ and $x_{1}\not \in v^{-k+1}$. Note that, if $x_1\in v^{-k+1}$ then we could have set $w_1=x_1$.  It then follows, from $(2)$, that $u^{-k} \times (u^{-k+1}\cup v^{-k+1}) \subseteq E(\hest)$. In particular $x_1\rightarrow y_1$, so we could have set $w_1=y_1$, contradiction.
This proves the theorem.
\end{proof}

It is known that GSP digraphs can be recognized in linear time. 
%\marginpar{Somehow this algorithm thing should be very simple at least for conservative DAGs}
In \cite{Valdes79:seriesparallel} it is given an algorithm that  given a DAG $\hest$,  with $n$ vertices and $m$ edges, recognizes in  $O(n+m)$  if $\hest$ is GSP.
We leave as an open question if Maltsev DAGs (or conservative Maltsev DAGs) can also be recognized in linear time.
In \cite{Valdes79:seriesparallel}  it is also mentioned an algorithm that checks in time linear to the size of the input, if $\hest$ is CBC.  This allows us to check if a given DAG, with $n$ vertices and $m$ edges,  is preserved by a Maltsev polymorphism in  $O(l(n+m))$-time, where $l$ is the number of levels of the digraph.






\section{Some Applications to the Constraint Satisfaction Problem}\label{appl_sect}
% changed Laci
%The logic programming language Datalog, and its fragments, is one of the tools to solve CSPs, in fact for  $\CSP(\bB)$  currently known to be in \ccNL \ or \ccL, the complement of $\CSP(\bB)$ can be defined in linear Datalog and symmetric Datalog, respectively, see  \cite{Bulatov08:duality,Dalmau05:linear,Egri/Larose/Tesson:2007:Symmetric}.
% By Theorem~\ref{retraction_theorem}, the core of a Maltsev digraph is either a directed path or a disjoint union of cycles, and for such digraphs the following is easy to show either directly, or noting the following (whose proof is in the appendix).
%\begin{corollary}\label{symDat}
%Let $H$ be a Maltsev digraph. Then the complement of $\CSP(H)$ can be defined in symmetric Datalog of constant width and therefore  $\CSP(H)$ is in \ccL.
%\end{corollary}
%MJ2: moved proof to appendix.




 The logic programming language Datalog is one of the main tools to solve
 $\CSP$s in \ccP. The fragments of Datalog called linear and symmetric
 Datalog are conjectured to contain all $\CSP$s in \ccNL\ and \ccL,
 respectively, see \cite{Bulatov08:duality,Dalmau05:linear,Egri/Larose/Tesson:2007:Symmetric}. A minor technicality is that it is actually the complement  of a $\CSP$ that can be defined in Datalog and its fragments, not the actual $\CSP$.

 By Theorem~\ref{retraction_theorem}, the core of a Maltsev digraph is
 either a directed path or a disjoint union of cycles, and for such
 digraphs, Corollary~\ref{symDat} is not difficult to show. For the proof below, note that the relevant definitions can be found, for example, in \cite{Egri/Larose/Tesson:2007:Symmetric}. Furthermore, if $0 \leq j \leq k$, then a symmetric Datalog program is said to have \textit{width $(j,k)$} if each rule of the program has at most $k$ variables, and at most $j$ variables in the head.
 
 \begin{corollary}\label{symDat}
 Let $H$ be a Maltsev digraph. Then the complement of $\CSP(H)$ can be
 defined in symmetric Datalog of width $(2,3)$, and therefore
  $\CSP(H)$ is in \ccL. \end{corollary}
  \begin{proof}[Proof Sketch.]
By Theorem~\ref{retraction_theorem}, we can assume that $H$ is a dipath or a disjoint union of cycles. Assume first that $H$ is the disjoint union of directed cycles. Then a digraph $G$ does not map to $H$ if and only if $G$ contains a connected component $C$ that does not map to any directed cycles in $H$. It is easy to see that $C$ does not map to a directed cycle of length $\ell$ if and only if $C$ contains a closed walk $v_1,v_2,\dots,v_1$ such that its net length is not $0 \bmod \ell$. This is easy to detect with a symmetric Datalog program of width $(2,3)$. For example, the program below works for $\CSP(H)$, where $H$ is the disjoint union of a directed 2-cycle and 3-cycle. It is straightforward to generalize this program to any set of cycles and to give a formal proof of correctness by induction. (For brevity, we did not include the symmetric pairs of the rules in the program below. Observe that those rules are easily seen to be harmless.)
\setcounter{equation}{0}

\begin{center}
\noindent\begin{minipage}[ht!]{3in}
\begin{center}
\begin{eqnarray}[rclc]
	I_1(s,x) &\leftarrow& E(s,x)\\
	I_1(s,x) &\leftarrow& E(x,s)\\	
	I_0(s,x) &\leftarrow& I_1(s,y) \wedge E(y,x)\\
	I_0(s,x) &\leftarrow& I_1(s,y) \wedge E(x,y)\\
	I_1(s,x) &\leftarrow& I_0(s,y) \wedge E(y,x)\\
	I_1(s,x) &\leftarrow& I_0(s,y) \wedge E(x,y)\\
	K(x) &\leftarrow& I_1(x,x)\\
	K(x) &\leftarrow& K(y) \wedge E(y,x)\\
	K(x) &\leftarrow& K(y) \wedge E(x,y)
\end{eqnarray}
\end{center}
\end{minipage}
\begin{minipage}[ht!]{3in}
\begin{center}
\begin{eqnarray}[rclc]
	J_0(s,s) &\leftarrow& K(s)\\	
	J_1(s,x) &\leftarrow& J_0(s,y) \wedge E(y,x)\\
	J_2(s,x) &\leftarrow& J_0(s,y) \wedge E(x,y)\\
	J_2(s,x) &\leftarrow& J_1(s,y) \wedge E(y,x)\\
	J_0(s,x) &\leftarrow& J_1(s,y) \wedge E(x,y)\\
	J_0(s,x) &\leftarrow& J_2(s,y) \wedge E(y,x)\\		
	J_1(s,x) &\leftarrow& J_2(s,y) \wedge E(x,y)\\		
	Goal &\leftarrow& J_1(x,x)\\
	Goal &\leftarrow& J_2(x,x)
\end{eqnarray}
\end{center}
\end{minipage}
\end{center}

In the program above, EDB E is the edge relation of the input graph, and $Goal$ is the goal predicate. IDB $I_1(a,b)$ ($I_0(a,b)$) is derived if and only if there is a walk of odd (even) net length from $a$ to $b$. Not that rule $(7)$ derives $K(c)$ if and only if there is a walk of odd net length starting at $a$ and ending at $c$. At this stage, we know that the connected component $C$ of the input digraph that contains $c$ has an odd cycle, so $C$ cannot map to the 2-cycle.  Using rules $(8)$ and $(9)$, the program can walk to any vertex of $C$. In the second part of the program, for example, the role of rule $(12)$ is the following. Assume that the variables of rule $(12)$ are instantiated to vertives of $G$ as $J_2(d,f) \leftarrow J_0(d,e) \wedge E(f,e)$. Then since $J_0(d,e)$ is derived, we know that there is a walk from $d$ to $e$ of net length $0 \bmod 3$. Since $E(f,e)$ is an edge of $G$, we know that there is a walk from $d$ to $f$ of net length $2 \bmod 3$, so the head $J_2(d,f)$ is derived.

Similar ideas work when $H$ is a directed path. For example, if $H$ is a dipath of length $2$, then we have to detect if $G$ contains a walk of net length at least $3$. If so, our program should accept, indicating that there is no homomorphism from $G$ to $H$. This can be done with a program of width $(1,2)$. If no such walk exists, then we still have to check that every walk from a vertex to itself has net length $0$. This can be easily done with a program of width $(2,3)$, similar in spirit to the program above.
\end{proof}


The \emph{list homomorphism problem} for a digraph $H$, $\ccLHOM(H)$,
  is the following decision problem. Given an input digraph $G$ and
 for each vertex $v \in V_G$ a list $L_v \subseteq V_H$, determine if
 there is a homomorphism $h$ from $G$ to $H$ such that for each $v
 \in V_G$, $h(v) \in L_v$. This problem is exactly $\CSP(H_u)$ where
 $H_u$ is the structure obtained by expanding the digraph $H$ with
 unary relations $U$, where $U$ runs through all non-empty subsets of
 $V_H$ . Using Corollary~\ref{cor:main}, the following corollary is
 easy to deduce.

 \begin{corollary}\label{LHOM} The  complement of
 $\ccLHOM(H)$ for a conservative Maltsev digraph $H$ can be defined
  in symmetric Datalog,  and therefore $\ccLHOM(H)$ is in $\ccL$. \end{corollary}
 \begin{proof}
Let $H$ be the digraph in the corollary. Assume the conservative Maltsev polymorphism is $mal$. Then by Corollary~\ref{cor:main}, $H$ also has a conservative majority polymorphism $maj$. Since $mal$ and $maj$ are conservative, they preserve any unary relations. Construct $\bB$ from $H$ as above. Then $mal$ and $maj$ is also a polymorphism of $\bB$. If a relational structure has a Maltsev and a majority polymorphism, then it is in symmetric Datalog by results of \cite{Dalmau/Larose:2008:Maltsev, Dalmau08:majority} (see also \cite{Egri:10:Symmetric}).
\end{proof}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\newpage
%\bibliographystyle{abbrv} \bibliography{mybib}

\begin{thebibliography}{10}

\bibitem{Barto/Bulin:10:CSP}
L.~Barto and J.~Bulin.
\newblock {CSP} dichotomy for special polyads.
\newblock {\em International Journal of Algebra and Computation 23/05}, pages
  1151--1174, 2013.

\bibitem{Barto/et_al:09:CSP}
L.~Barto, M.~Kozik, M.~Mar{\'o}ti, and T.~Niven.
\newblock {CSP} dichotomy for special triads.
\newblock {\em Proceedings of the AMS}, 137:2921--2934, 2009.

\bibitem{Barto:2008:Graphs}
L.~Barto, M.~Kozik, and T.~Niven.
\newblock Graphs, polymorphisms and the complexity of homomorphism problems.
\newblock In {\em Proceedings of the 40th annual ACM symposium on Theory of Computing}, STOC '08, pages 789--796, 2008.

\bibitem{Bulatov/Dalmau:06:Simple}
A.~Bulatov and V.~Dalmau.
\newblock A simple algorithm for {M}al'tsev constraints.
\newblock {\em SIAM Journal on Computing}, 36(1):16--27, 2006.

\bibitem{Bulatov/Jeavons/Krokhin:2000:Constraint}
A.~Bulatov, P.~Jeavons, and A.~Krokhin.
\newblock Constraint satisfaction problems and finite algebras.
\newblock In {\em Proceedings of the 27th International Colloquium on Automata,
  Languages and Programming}, ICALP '00, pages 272--282, 2000.

\bibitem{Bulatov/Jeavons/Krokhin:2005:Classifying}
A.~Bulatov, P.~Jeavons, and A.~Krokhin.
\newblock Classifying the complexity of constraints using finite algebras.
\newblock {\em SIAM Journal on Computing}, 34(3):720--742, 2005.

\bibitem{Bulatov08:duality}
A.~Bulatov, A.~Krokhin, and B.~Larose.
\newblock Dualities for constraint satisfaction problems.
\newblock In {\em LNCS Surveys on Complexity of Constraints}, volume 5250,
  pages 93--124. 2008.

\bibitem{BDJN}
J.~Bulin, D.~Delic, M.~Jackson, and T.~Niven.
\newblock On the reduction of {CSP} dichotomy to digraphs.
\newblock In {\em Theory and Practice of Constraint Programming}, CP2013, pages
  184--199, 2013.

\bibitem{carvalho2011maltsev}
C.~Carvalho, L.~Egri, M.~Jackson, and T.~Niven.
\newblock On maltsev digraphs.
\newblock In {\em Computer Science--Theory and Applications}, pages 181--194.
  Springer, 2011.

\bibitem{Dalmau05:linear}
V.~Dalmau.
\newblock Linear {D}atalog and bounded path duality of relational structures.
\newblock {\em Logical Methods in Computer Science}, 1:1--32, 2005.

\bibitem{Dalmau08:majority}
V.~Dalmau and A.~Krokhin.
\newblock Majority constraints have bounded pathwidth duality.
\newblock {\em European Journal of Combinatorics}, 29(4):821--837, 2008.

\bibitem{Dalmau/Larose:2008:Maltsev}
V.~Dalmau and B.~Larose.
\newblock Maltsev + {D}atalog {$\Rightarrow$} {S}ymmetric {D}atalog.
\newblock In {\em Proceedings of the 23rd IEEE Symposium on Logic in Computer
  Science}, LICS '08, pages 297--306, 2008.

\bibitem{Dyer/Richerby:10:Complexity}
M.~E. Dyer and D.~Richerby.
\newblock On the complexity of \#{CSP}.
\newblock In {\em Proceedings of the 42nd ACM Symposium on Theory of
  Computing}, STOC '10, pages 725--734, 2010.

\bibitem{Egri:10:Symmetric}
L.~Egri.
\newblock On constraint satisfaction problems below {P}.
\newblock {\em Journal of Logic and Computation}, 2014.

\bibitem{EgriHellLaroseRafiey13}
L.~Egri, P.~Hell, B.~Larose, and A.~Rafiey.
\newblock Space complexity of list {H}-colouring: a dichotomy.
\newblock SODA 2014, pages 349--365.

\bibitem{Egri/et_al:2009:Complexity}
L.~Egri, A.~Krokhin, B.~Larose, and P.~Tesson.
\newblock The complexity of the list homomorphism problem for graphs.
\newblock In {\em Proceedings of the 27th International Symposium on
  Theoretical Aspects of Computer Science}, STACS '10, pages 335--346, 2010.

\bibitem{Egri/Larose/Tesson:2007:Symmetric}
L.~Egri, B.~Larose, and P.~Tesson.
\newblock Symmetric {D}atalog and constraint satisfaction problems in logspace.
\newblock In {\em Proceedings of the 22nd Annual IEEE Symposium on Logic in
  Computer Science}, LICS '07, pages 193--202, 2007.

\bibitem{Hagemann/Mitschke:73:n-permutable}
J.~Hagemann and A.~Mitschke.
\newblock On $n$-permutable congruences.
\newblock {\em Algebra Universalis}, 3:8--12, 1973.

\bibitem{Hell/Nesetril:90:H-Coloring}
P.~Hell and J.~Ne\v{s}et\v{r}il.
\newblock On the complexity of {$H$}-coloring.
\newblock {\em Journal of Combinatorial Theory, Series B}, 48:92--110, 1990.

\bibitem{Hell/Rafiey:10:Dichotomy}
P.~Hell and A.~Rafiey.
\newblock The dichotomy of list homomorphisms for digraphs.
\newblock In {\em Proceedings of the ACM-SIAM Symposium on Discrete
  Algorithms}, SODA '11, pages 1703--1713, 2011.

\bibitem{Jeavons/Cohen/Gyssens:1997:Closure}
P.~Jeavons, D.~Cohen, and M.~Gyssens.
\newblock Closure properties of constraints.
\newblock {\em J. ACM}, 44(4):527--548, 1997.

\bibitem{Kazda:10:Maltsev}
A.~Kazda.
\newblock Maltsev digraphs have a majority polymorphism.
\newblock {\em European Journal of Combinatorics}, 32:390--397, 2011.

\bibitem{Maroti/McKenzie:07:Existence}
M.~Mar\'oti and R.~McKenzie.
\newblock Existence theorems for weakly symmetric operations.
\newblock {\em Algebra Universalis}, 59(3-4):463--489, 2008.

\bibitem{Mohring89:tractableordered}
R.~H. M{\"o}hring.
\newblock Computationally tractable classes of ordered sets.
\newblock In {\em Algorithms and order ({O}ttawa, {ON}, 1987)}, pages 105--193.
  Kluwer Acad. Publ., Dordrecht, 1989.

\bibitem{Valdes79:seriesparallel}
J.~Valdes, R.~E. Tarjan, and E.~L. Lawler.
\newblock The recognition of series parallel digraphs.
\newblock {\em SIAM J. Comput.}, 11(2):298--313, 1982.

\end{thebibliography}








\end{document}
