Lower Bounds for the Graph Homomorphism Problem

摘要

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 bounds for HOM under the Exponential Time Hypothesis (ETH) assumption. The main result is a lower bound 2~(Ω(n log h/log log h)). This rules out the existence of a single-exponential algorithm and shows that the trivial upper bound 2~(O(nlogh)) 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 O(h~n) upper bound can be improved to O(h~(vc(G))) where vc(G) is the minimum size of a vertex cover of G. The second lower bound h~(Ω(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(Δ(H)))~n and (f(tw(H)))~n where Δ(H) is the maximum degree of H and 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 χ(H) does not exceed tw(H) and Δ(H)+1, it is natural to ask whether similar upper bounds with respect to χ(H) can be obtained. We provide a negative answer by establishing a lower bound (f(χ(H)))~n for every function f. We also observe that similar lower bounds can be obtained for locally injective homomorphisms.