Editing Graph homomorphism (section)

==Computational complexity==
In the graph homomorphism problem, an instance is a pair of graphs (''G'',''H'') and a solution is a homomorphism from ''G'' to ''H''. The general [[decision problem]], asking whether there is any solution, is [[NP-complete]].{{sfn|Bodirsky|2007|loc=§1.3}} However, limiting allowed instances gives rise to a variety of different problems, some of which are much easier to solve. Methods that apply when restraining the left side  ''G'' are very different than for the right side ''H'', but in each case a dichotomy (a sharp boundary between easy and hard cases) is known or conjectured.

===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.

===Homomorphisms from a fixed family of graphs===
The homomorphism problem with a single fixed graph ''G'' on left side of input instances can be solved by [[Brute-force search|brute-force]] in time |''V''(''H'')|<sup>O(|''V''(''G'')|)</sup>, so polynomial in the size of the input graph ''H''.<ref>{{citation
 | last1 = Cygan | first1 = Marek
 | last2 = Fomin | first2 = Fedor V. | author2-link = Fedor Fomin
 | last3 = Golovnev | first3 = Alexander
 | last4 = Kulikov | first4 = Alexander S.
 | last5 = Mihajlin | first5 = Ivan
 | last6 = Pachocki | first6 = Jakub
 | last7 = Socala | first7 = Arkadiusz
 | editor-last = Krauthgamer | editor-first = Robert
 | arxiv = 1507.03738
 | contribution = Tight bounds for graph homomorphism and subgraph isomorphism
 | doi = 10.1137/1.9781611974331.ch112
 | isbn = 978-1-611974-33-1
 | pages = 1643–1649
 | publisher = [[Society for Industrial and Applied Mathematics]]
 | title = Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10–12, 2016
 | year = 2016}}</ref> In other words, the problem is trivially in P for graphs ''G'' of bounded size. The interesting question is then what other properties of ''G'', beside size, make polynomial algorithms possible.

The crucial property turns out to be [[treewidth]], a measure of how tree-like the graph is. For a graph ''G'' of treewidth at most ''k'' and a graph ''H'', the homomorphism problem can be solved in time |''V''(''H'')|<sup>O(''k'')</sup> with a standard [[dynamic programming]] approach. In fact, it is enough to assume that the core of ''G'' has treewidth at most ''k''. This holds even if the core is not known.<ref>{{citation
 | last1 = Dalmau | first1 = Víctor
 | last2 = Kolaitis | first2 = Phokion G.
 | last3 = Vardi | first3 = Moshe Y. | author3-link = Moshe Vardi
 | editor-last = Van Hentenryck | editor-first = Pascal
 | contribution = Constraint satisfaction, bounded treewidth, and finite-variable logics
 | doi = 10.1007/3-540-46135-3_21
 | pages = 310–326
 | publisher = Springer
 | series = Lecture Notes in Computer Science
 | title = Principles and Practice of Constraint Programming – CP 2002, 8th International Conference, CP 2002, Ithaca, NY, USA, September 9–13, 2002, Proceedings
 | volume = 2470
 | year = 2002| isbn = 978-3-540-44120-5
 }}</ref><ref name="Grohe">{{citation|first=Martin|last=Grohe|authorlink=Martin Grohe|title=The complexity of homomorphism and constraint satisfaction problems seen from the other side|volume=54|issue=1|pages=1–es|year=2007|journal=[[Journal of the ACM]]|doi=10.1145/1206035.1206036|s2cid=11797906}}</ref>

The exponent in the |''V''(''H'')|<sup>O(''k'')</sup>-time algorithm cannot be lowered significantly: no algorithm with running time |''V''(''H'')|<sup>o(tw(''G'') /log tw(''G''))</sup> exists, assuming the [[exponential time hypothesis]] (ETH), even if the inputs are restricted to any class of graphs of unbounded treewidth.<ref name="marx">{{citation|first=Dániel|last=Marx|title=Can You Beat Treewidth?|journal=[[Theory of Computing (journal)|Theory of Computing]]|year=2010|volume=6|pages=85–112|doi=10.4086/toc.2010.v006a005|doi-access=free}}</ref>
The ETH is an unproven assumption similar to [[P versus NP problem|P ≠ NP]], but stronger.
Under the same assumption, there are also essentially no other properties that can be used to get polynomial time algorithms. This is formalized as follows:
: '''Theorem''' ([[Martin Grohe|Grohe]]): For a [[Recursive set|computable]] class of graphs <math>\mathcal{G}</math>, the homomorphism problem for instances <math>(G,H)</math> with <math>G \in \mathcal{G}</math> is in P if and only if graphs in <math>\mathcal{G}</math> have cores of bounded treewidth (assuming ETH).<ref name="Grohe"/>

One can ask whether the problem is at least solvable in a time arbitrarily highly dependent on ''G'', but with a fixed polynomial dependency on the size of ''H''.
The answer is again positive if we limit ''G'' to a class of graphs with cores of bounded treewidth, and negative for every other class.<ref name="Grohe"/>
In the language of [[parameterized complexity]], this formally states that the homomorphism problem in <math>\mathcal{G}</math> parameterized by the size (number of edges) of ''G'' exhibits a dichotomy. It is [[fixed-parameter tractable]] if graphs in <math>\mathcal{G}</math> have cores of bounded treewidth, and [[Parameterized complexity#W.5B1.5D|W[1]]]-complete otherwise.

The same statements hold more generally for constraint satisfaction problems (or for relational structures, in other words). The only assumption needed is that constraints can involve only a bounded number of variables (all relations are of some bounded arity, 2 in the case of graphs). The relevant parameter is then the treewidth of the [[primal constraint graph]].<ref name="marx"/>