2010/04/16 by Pavol Hell, Hell, Pavol, Arash Rafiey +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Constraint Satisfaction and Optimization #FOS: Computer and information sciences #FOS: Mathematics #cs.CC #math.CO #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1004.2908
openalex publication_date 2010/04/16 · arxiv created 2010/04/20 · arxiv updated 2010/04/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.