2015/02/19 by Fedor V. Fomin, Alexander Golovnev, Fomin, Fedor V. +5 · 1 citation
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1502.05447
openalex publication_date 2015/02/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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Ω( (n log h)/(log log h)). This rules out the existence of a single-exponential algorithm and shows that the trivial upper bound 2^\mathcal 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 \mathcal O(hn) upper bound can be improved to \mathcal O(hvc(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 to this question by establishing a lower bound (f(χ(H)))n for any function f. We also observe that similar lower bounds can be obtained for locally injective homomorphisms.