FINE-GRAINED COMPLEXITY OF THE GRAPH HOMOMORPHISM PROBLEM FOR BOUNDED-TREEWIDTH GRAPHS

For a fixed graph H, by Hom( H) we denote the computational problem which asks whether a given graph G admits a homomorphism to H, i.e., an edge-preserving mapping from V (G) to V (H). As Hom( K-k) is equivalent to k-Coloring, graph homomorphisms can be seen as generalizations of colorings. It is known that Hom(H) is polynomial-time solvable if H is bipartite or has a vertex with a loop, and NP-complete otherwise [Hell and Nesetril, J. Comb. Theory Ser. B, 48 (1990), pp. 92-110]. In this paper we are interested in the complexity of the problem, parameterized by the treewidth of the input graph G. If G has n vertices and is given along with its tree decomposition of width tw(G), then the problem can be solved in time jV (H)jtw(G) nO(1), using a straightforward dynamic programming. We explore whether this bound can be improved. We show that if H is a projective core, then the existence of such a faster algorithm is unlikely: assuming the Strong Exponential Time Hypothesis, the Hom(H) problem cannot be solved in time (jV (H)j - epsilon)tw(G) nO(1), for any " > 0. This result provides a full complexity characterization for a large class of graphs H, as almost all graphs are projective cores. We also notice that the naive algorithm can be improved for some graphs H and show a complexity classification for all graphs H, assuming two conjectures from algebraic graph theory. In particular, there are no known graphs H which are not covered by our result.