  In this paper we study the class of bi-arc digraphs, important from two
seemingly unrelated perspectives. On the one hand, they are precisely the
digraphs that admit certain polymorphisms of interest in the study of
constraint satisfaction problems; on the other hand, they are a very broad
generalization of interval graphs.
  Bi-arc digraphs is the class of digraphs that admit conservative semilattice
polymorphisms. There is much interest in understanding structures that admit
particular types of polymorphisms, and especially in their recognition
algorithms. (Such problems are referred to as metaproblems.) Surprisingly, the
class of bi-arc digraphs also describes the class of digraphs that admit
certain other kinds of conservative polymorphisms. Thus solving the recognition
problem for bi-arc digraphs solves the metaproblem for digraphs for several
types of conservative polymorphisms. The complexity of the recognition problem
for digraphs with conservative semilattice polymorphisms was an open problem,
while it was known to be NP-complete for certain more complex relational
structures. We complement our result by providing a complete dichotomy
classification of which general relational structures have polynomial or
NP-complete recognition problems for the existence of conservative semilattice
polymorphisms.
  Bi-arc digraphs also generalizes the class of interval graphs; in fact it
reduces to the class of interval graphs for symmetric and reflexive digraphs.
It is much broader than interval graphs and includes other generalizations of
interval graphs such as co-threshold tolerance graphs and adjusted interval
digraphs. Yet, it is still a reasonable extension of interval graphs, in the
sense that it keeps much of the appeal of interval graphs.
  Our main result is a forbidden obstruction characterization of, and a
polynomial recognition for, the class of bi-arc digraphs.
