Bi-arc Digraphs: Recognition Algorithm and Applications

We study the class of bi-arc digraphs, important from two seemingly unrelated perspectives. On the one hand, they are a broad generalization of interval graphs that include other popular generalizations of interval graphs, such as co-threshold tolerance graphs and adjusted interval digraphs. On the other hand, they are precisely the digraphs that admit the so-called conservative semilattice polymorphisms, also known as min orderings or X-underbar enumerations. These digraphs are generally interesting in studying graph homomorphisms and constraint satisfaction problems. Our main result is a forbidden obstruction characterization of the class of bi-arc digraphs and a polynomial-time recognition algorithm. In addition, we show that they are precisely the digraphs that admit certain other kinds of conservative polymorphisms, thereby collapsing these polymorphism types in the class of digraphs. 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.