The homomorphism problem $\text{Hom}(\mathcal{G}, \mathcal{H})$ for two classes $\mathcal{G}$ and $\mathcal{H}$ of graphs is defined as follows:
Input: a graph $G$ in $\mathcal{G}$, a graph $H$ in $\mathcal{H}$
Output: decide if there is a homomorphism from $G$ to $H$, i.e., a mapping $h$ from the vertices of $G$ to those of $H$ such that, for any edge $\{x, y\}$ of $G$, $\{h(x), h(y)\}$ is an edge of $H$.
For each $k \in \mathbb{N}$, I will call $\mathcal{T}_k$ the class of the graphs of treewidth at most $k$. I'm interested in the problem $\text{Hom}(\mathcal{T}_k, \mathcal{T}_k)$, which I see as a parameterized problem (by the treewidth bound $k$). My question is: what is the complexity of this parameterized problem? Is it known to be FPT? or is it W[1]-hard?
Here are some things that I found about the $\text{Hom}$ problem, but which do not help me answer the question. (I write $-$ for the class of all graphs.)
- http://www.sciencedirect.com/science/article/pii/009589569090132J: If $\mathcal{H}$ is bipartite then $\text{Hom}(-, \mathcal{H})$ is in PTIME, otherwise it is NP-complete, but of course the NP-hardness relies on allowing arbitrary $G$.
- http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.86.9013&rep=rep1&type=pdf: If the treewidth of $\mathcal{G}$ (modulo homomorphic equivalence) is bounded by a constant then $\text{Hom}(\mathcal{G}, -)$ is in PTIME (and otherwise it isn't, assuming FPT != W[1]). Hence, in particular my problem $\text{Hom}(\mathcal{T}_k, \mathcal{T}_k)$ is in PTIME for fixed $k$, but this doesn't tell me what is the dependency on the parameter.
- From Flum and Grohe's book Parameterized Complexity Theory, Corollary 13.17: The problem $\text{Hom}(\mathcal{T}_k, -)$ is FPT when parameterized by the size of $G$ (but I am parameterizing by the treewidth)
- http://users.uoa.gr/~sedthilk/papers/homo.pdf, Corollary 3.2: When fixing a specific graph $H$, the problem $\text{Hom}(\mathcal{T}_k, \{H\})$, parameterized by k, is FPT (this even holds for more complicated counting variants), but I do not want to restrict to fixed $H$.
