The graph homomorphism problem (HOM) asks whether the vertices of a given $n$-vertex graph $G$ can be mapped to the vertices of a given $h$-vertex graph $H$ such that each edge of $G$ is mapped to an edge of $H$. The problem generalizes the graph coloring problem and at the same time can be viewed as a special case of the $2$-CSP problem. In this paper, we prove several lower bound for HOM under the Exponential Time Hypothesis (ETH) assumption. The main result is a lower bound $2^{ \Omega\left( \frac{ n \log h}{ \log \log h}\right)}$. This rules out the existence of a single-exponential algorithm and shows that the trivial upper bound $2^{ { \mathcal O}(n\log{ h})}$ is almost asymptotically tight. We also investigate what properties of graphs $G$ and $H$ make it difficult to solve HOM$(G,H)$. An easy observation is that an ${ \mathcal O}(h^n)$ upper bound can be improved to ${ \mathcal O}(h^{ \operatorname{ vc}(G)})$ where $\operatorname{ vc}(G)$ is the minimum size of a vertex cover of $G$. The second lower bound $h^{ \Omega(\operatorname{ vc}(G))}$ shows that the upper bound is asymptotically tight. As to the properties of the "right-hand side" graph $H$, it is known that HOM$(G,H)$ can be solved in time $(f(\Delta(H)))^n$ and $(f(\operatorname{ tw}(H)))^n$ where $\Delta(H)$ is the maximum degree of $H$ and $\operatorname{ tw}(H)$ is the treewidth of $H$. This gives single-exponential algorithms for graphs of bounded maximum degree or bounded treewidth. Since the chromatic number $\chi(H)$ does not exceed $\operatorname{ tw}(H)$ and $\Delta(H)+1$, it is natural to ask whether similar upper bounds with respect to $\chi(H)$ can be obtained. We provide a negative answer to this question by establishing a lower bound $(f(\chi(H)))^n$ for any function $f$. We also observe that similar lower bounds can be obtained for locally injective homomorphisms.
Categories: cs.DS