18
$\begingroup$

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$.
Improve this question
$\endgroup$
1
  • $\begingroup$ This question is still open, but one remark: there is an FPT algorithm parameterized by treewidth for the graph isomorphism problem, here: epubs.siam.org/doi/abs/10.1137/… (Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh, "Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth", SICOMP.) As far as I know, unfortunately, this does not say anything about the homomorphism problem. $\endgroup$
    – a3nm
    Apr 22, 2022 at 21:26

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.