Counting list homomorphisms from graphs of bounded treewidth: tight complexity bounds

Summary

The goal of this work is to give precise bounds on the counting complexity of a family of generalized coloring problems (list homomorphisms) on bounded-treewidth graphs. Given graphs $G$, $H$, and lists $L(v)\subseteq V(H)$ for every $v\in V(G)$, a {\em list homomorphism} is a function $f:V(G)\to V(H)$ that preserves the edges (i.e., $uv\in E(G)$ implies $f(u)f(v)\in E(H)$) and respects the lists (i.e., $f(v)\in L(v))$. Standard techniques show that if $G$ is given with a tree decomposition of width $t$, then the number of list homomorphisms can be counted in time $|V(H)|^t\cdot n^{\mathcal{O}(1)}$. Our main result is determining, for every fixed graph $H$, how much the base $|V(H)|$ in the running time can be improved. For a connected graph $H$ we define $\operatorname{irr}(H)$ in the following way: if $H$ has a loop or is nonbipartite, then $\operatorname{irr}(H)$ is the maximum size of a set $S\subseteq V(H)$ where any two vertices have different neighborhoods; if $H$ is bipartite, then $\operatorname{irr}(H)$ is the maximum size of such a set that is fully in one of the bipartition classes. For disconnected $H$, we define $\operatorname{irr}(H)$ as the maximum of $\operatorname{irr}(C)$ over every connected component $C$ of $H$. It follows from earlier results that if $\operatorname{irr}(H)=1$, then the problem of counting list homomorphisms to $H$ is polynomial-time solvable, and otherwise it is \#P-hard. We show that, for every fixed graph $H$, the number of list homomorphisms from $(G,L)$ to $H$ \begin{itemize} \item can be counted in time $\operatorname{irr}(H)^t\cdot n^{\mathcal{O}(1)}$ if a tree decomposition of $G$ having width at most $t$ is given in the input, and \item given that $\operatorname{irr}(H)\ge 2$, cannot be counted in time $(\operatorname{irr}(H)-\epsilon)^t\cdot n^{\mathcal{O}(1)}$ for any $\epsilon>0$, even if a tree decomposition of $G$ having width at most $t$ is given in the input, unless the Counting Strong Exponential-Time Hypothesis (\#SETH) fails. \end{itemize} Thereby we give a precise and complete complexity classification featuring matching upper and lower bounds for all target graphs with or without loops.