Dichotomy Conjecture for Constraint Tillfredsställelse Problem har verifierats för konservativa problem (eller, motsvarande, för lista homomorphism problem) av Andrei Bulatov. Ett tidigare fall av denna dikotomi, för lista homomorfismer till oriktade grafer, kom med en elegant strukturell skillnad mellan de dragbara och svåråtkomliga fall. Sådan strukturell karakterisering saknas i Bulatovs klassificering, och Bulatov frågade om man kan hittas. Vi ger ett svar när det gäller digrafer. I processen ger vi förbjudna strukturkarakteriseringar av förekomsten av vissa polymorfismer som är relevanta i Bulatovs dikotomiklassificering. Nyckelbegreppet vi introducerar är en digrafasteroid trippel (DAT). Dikotomi tar sedan följande form. Om en digraf H har en DAT, då listan homomorfism problem för H är NP-komplett; och en DAT-fri digraf H har en polynom tid solvable lista homomorphism problem. DAT-fria digrafer kan kännas igen i polynom tid. Det följer av våra resultat att listan homomorfism problem för en DAT-fri digraf H kan lösas med en lokal konsekvent algoritm (av bredd (2,3)).
En strukturell skillnad mellan dragbar och NP-fullständig lista homomorfism problem för digrafer hittades i REF.
The dichotomy of list homomorphisms for digraphs
{'venue': "SODA '11", 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}