Editing Graph homomorphism (section)

===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"/>