In the list homomorphism problem, the input consists of two graphs G and H, together with a list L(v)⊂V(H) for every vertex v ∈ V(G). The task is to find a homomorphism φ:V(G) -> V(H) respecting the lists, that is, we have that φ(v) ∈ L(v) for every v ∈ V(H) and if u and v are adjacent in G, then φ(u) and φ(v) are adjacent in H. If H is a fixed graph, then the problem is denoted by LHOM(H). Feder, Hell, and Huang provided the complexity dichotomy for the problem [Feder, Hell, Huang, JGT 2003].
We explore the complexity of the problem parameterized by the treewidth tw(G) of the input graph G. If a tree decomposition of G of width tw(G) is given in the input, then the problem can be solved in time |V(H)|^tw(G) * n^O(1) by naive dynamic programming. Our main result completely reveals when and by exactly how much this naive algorithm can be improved. We introduce a simple combinatorial invariant i^*(H), which is based on the existence of certain decompositions and incomparable sets, and show that this number should appear as the base of the exponent in the best possible running time. Specifically, we prove for every graph H, for which LHom(H) is NP-hard:
- If a tree decomposition of width tw(G) is given in the input, then the
problem can be solved in time i^*(H)^tw(G) * n^O(1).
- Assuming the Strong Exponential-Time Hypothesis (SETH), the problem cannot be solved in time (i^*(H)-ε)^tw(G) * n^O(1) for any ε>0.
Thus by matching upper and lower bounds, our result exactly characterizes for every fixed H the complexity of LHOM(H) parameterized by treewidth.
The results are obtained as a joint work with Karolina Okrasa and Paweł Rzążewski.