  The Dichotomy Conjecture for constraint satisfaction problems has been
verified for conservative problems (or, equivalently, for list homomorphism
problems) by Andrei Bulatov. An earlier case of this dichotomy, for list
homomorphisms to undirected graphs, came with an elegant structural distinction
between the tractable and intractable cases. Such structural characterization
is absent in Bulatov's classification, and Bulatov asked whether one can be
found. We provide an answer in the case of digraphs; the technique will apply
in a broader context. The key concept we introduce is that of a digraph
asteroidal triple (DAT). The dichotomy then takes the following form. If a
digraph H has a DAT, then the list homomorphism problem for H is NP-complete;
and a DAT-free digraph H has a polynomial time solvable list homomorphism
problem. DAT-free graphs can be recognized in polynomial time.
