The Dichotomy of List Homomorphisms for Digraphs

Details The Dichotomy of List Homomorphisms for Digraphs The Dichotomy of List Homomorphisms for Digraphs

2010-04-16

arxiv.org/abs/1004.2908v2

Computer Science

Computational Complexity

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

The Dichotomy of List Homomorphisms for Digraphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Dichotomy of List Homomorphisms for Digraphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Dichotomy of List Homomorphisms for Digraphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-624539