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$.
$\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

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.