Finding list homomorphisms from bounded-treewidth graphs to reflexive graphs: a complete complexity characterization

In the list homomorphism problem, the input consists of two graphs G and H, together with a list L(v) \subseteq V(H) for every vertex v\in V(G). The task is to find a homomorphism

\phi:V(G)\to V(H) respecting the lists, that is, we have that  \phi(v)\in L(v) for every v\in V(H) and if u and v are adjacent in G, then \phi(u) and \phi(v) are adjacent in H. If H is a fixed graph, then the problem is denoted by LHom(H). We consider the reflexive version of the problem, where we assume that every vertex in H has a self-loop. If is known that reflexive LHom(H) is

polynomial-time solvable if H is an interval graph and it is NP-complete otherwise [Feder and Hell, JCTB 1998].

 

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)}\cdot 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 non-interval reflexive graph H that

 

- item 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)}\cdot n^{O(1)}.

- Assuming the Strong Exponential-Time Hypothesis (SETH), the problem cannot be solved in time (i^*(H)-\epsilon)^{tw(G)}\cdot n^{O(1)} for any \epsilon>0.

 

 

Thus by matching upper and lower bounds, our result exactly characterizes for every fixed H the complexity of reflexive LHom(H) parameterized by treewidth.

 

The results are obtained as a joint work with Daniel Marx and Laszlo Egri.