  The Dichotomy Conjecture for constraint satisfaction problems (CSPs) states
that every CSP is in P or is NP-complete (Feder-Vardi, 1993). It has been
verified for conservative problems (also known as list homomorphism problems)
by A. Bulatov (2003). We augment this result by showing that for digraph
templates H, every conservative CSP, denoted LHOM(H), is solvable in logspace
or is hard for NL. More precisely, we introduce a digraph structure we call a
circular N, and prove the following dichotomy: if H contains no circular N then
LHOM(H) admits a logspace algorithm, and otherwise LHOM(H) is hard for NL. Our
algorithm operates by reducing the lists in a complex manner based on a novel
decomposition of an auxiliary digraph, combined with repeated applications of
Reingold's algorithm for undirected reachability (2005). We also prove an
algebraic version of this dichotomy: the digraphs without a circular N are
precisely those that admit a finite chain of polymorphisms satisfying the
Hagemann-Mitschke identities. This confirms a conjecture of Larose and Tesson
(2007) for LHOM(H). Moreover, we show that the presence of a circular N can be
decided in time polynomial in the size of H.
