Editing Graph homomorphism (section)

===Homomorphisms to a fixed graph===
The homomorphism problem with a fixed graph ''H'' on the right side of each instance is also called the ''H''-coloring problem. When ''H'' is the complete graph ''K''<sub>''k''</sub>, this is the [[Graph coloring#Computational complexity|graph ''k''-coloring problem]], which is solvable in polynomial time for ''k'' = 0, 1, 2, and [[NP-complete]] otherwise.{{sfn|Hell|Nešetřil|2004|loc=§5.1}}
In particular, ''K''<sub>2</sub>-colorability of a graph ''G'' is equivalent to ''G'' being [[Bipartite graph#Testing bipartiteness|bipartite]], which can be tested in linear time.
More generally, whenever ''H'' is a bipartite graph, ''H''-colorability is equivalent to ''K''<sub>2</sub>-colorability (or ''K''<sub>''0''</sub> / ''K''<sub>''1''</sub>-colorability when ''H'' is empty/edgeless), hence equally easy to decide.{{sfn|Hell|Nešetřil|2004|loc=Proposition 5.1}}
[[Pavol Hell]] and [[Jaroslav Nešetřil]] proved that, for undirected graphs, no other case is tractable:

: '''Hell–Nešetřil theorem''' (1990): The ''H''-coloring problem is in P when ''H'' is bipartite and NP-complete otherwise.{{sfn|Hell|Nešetřil|2004|loc=§5.2}}<ref>{{citation|first1=Pavol|last1=Hell|author1-link=Pavol Hell|first2=Jaroslav|last2=Nešetřil|author2-link=Jaroslav Nešetřil|title=On the complexity of H-coloring|year=1990|journal=[[Journal of Combinatorial Theory]] | series=Series B|volume=48|issue=1|pages=92–110|doi=10.1016/0095-8956(90)90132-J|doi-access=free}}</ref>

This is also known as the ''dichotomy theorem'' for (undirected) graph homomorphisms, since it divides ''H''-coloring problems into NP-complete or P problems, with no [[NP-intermediate|intermediate]] cases.
For directed graphs, the situation is more complicated and in fact equivalent to the much more general question of characterizing the [[Complexity of constraint satisfaction|complexity of constraint satisfaction problems]].{{sfn|Hell|Nešetřil|2004|loc=§5.3}}
It turns out that ''H''-coloring problems for directed graphs are just as general and as diverse as CSPs with any other kinds of constraints.{{sfn|Hell|Nešetřil|2004|loc=Theorem 5.14}}<ref name="FederVardi">{{citation|first1=Tomás|last1=Feder|first2=Moshe Y.|last2=Vardi|author2-link=Moshe Y. Vardi|title=The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory|year=1998|journal=[[SIAM Journal on Computing]]|volume=28|issue=1|pages=57–104|doi=10.1137/S0097539794266766|url=http://theory.stanford.edu/~tomas/constraint.ps}}</ref> Formally, a (finite) ''constraint language'' (or ''template'') ''Γ'' is a finite domain and a finite set of relations over this domain. CSP(''Γ'') is the constraint satisfaction problem where instances are only allowed to use constraints in ''Γ''. 
: '''Theorem''' (Feder, [[Moshe Y. Vardi|Vardi]] 1998): For every constraint language ''Γ'', the problem CSP(''Γ'') is equivalent under [[polynomial-time reduction]]s to some ''H''-coloring problem, for some directed graph ''H''.<ref name="FederVardi"/>

Intuitively, this means that every algorithmic technique or complexity result that applies to ''H''-coloring problems for directed graphs ''H'' applies just as well to general CSPs. In particular, one can ask whether the Hell–Nešetřil theorem can be extended to directed graphs. By the above theorem, this is equivalent to the Feder–Vardi conjecture (aka CSP conjecture, dichotomy conjecture) on CSP dichotomy, which states that for every constraint language ''Γ'', CSP(''Γ'') is NP-complete or in P.{{sfn|Bodirsky|2007|loc=§1.3}} This conjecture was proved in 2017 independently by Dmitry Zhuk and Andrei Bulatov, leading to the following corollary:
: '''Corollary''' (Bulatov 2017; Zhuk 2017): The ''H''-coloring problem on directed graphs, for a fixed ''H'', is either in P or NP-complete.