Paper Info
Title
The dichotomy of list homomorphisms for digraphs
Abstract
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. In the process we give forbidden structure characterizations of the existence of certain polymorphisms relevant in Bulatov's dichotomy classification. 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 digraphs can be recognized in polynomial time. It follows from our results that the list homomorphism problem for a DAT-free digraph H can be solved by a local consistency algorithm (of width (2, 3)).
Year
DOI
Venue
2011
10.5555/2133036.2133167
SODA '11: 22nd ACM-SIAM Symposium on Discrete Algorithms San Francisco California January, 2011
Keywords
DocType
Volume
dat-free digraph h,homomorphism problem,list homomorphisms,polynomial time solvable list,conservative problem,dat-free digraph,digraph h,andrei bulatov,digraph asteroidal,list homomorphism problem,polymorphism,polynomial time,constraint satisfaction problem
Conference
abs/1004.2908
ISBN
Citations 
PageRank 
978-1-61197-251-1
14
0.63
References 
Authors
26
2
Name
Order
Citations
PageRank
Pavol Hell12638288.75
Arash Rafiey233928.08