The problem of determining the existence of a homomorphism from a graph ( G ) to a graph ( H ), where both ( G ) and ( H ) have treewidth at most ( k ), parameterized by ( k ), is known to be W[1]-hard.

Key Reasoning:

1. Problem Definition: The homomorphism problem ( \text{Hom}(T_k, T_k) ) asks whether there exists a mapping ( h: V(G) \to V(H) ) preserving edges, given (...

Short answer: Hom(Tk, Tk) is W[1]-hard (indeed W[1]-complete) when parameterized by k. In particular, although for every fixed k the problem is solvable in polynomial time (XP), there is no f(k)·nO(1)-time algorithm unless FPT = W[1]. Moreover, under ETH there are matching lower bounds ruling out substantially faster FPT runtimes.

Why W[1]-hard

• A convenient source of hardness is Partitioned (a....

Below is what is known (and not known) about the two‐sided tree–width–parameterized homomorphism problem

Input:  two graphs G,H with tw(G)≤k and tw(H)≤k  
Parameter:  k  
Question:  is there a homomorphism h:V(G)→V(H)?

1. A trivial XP–algorithm.
   – First run Bodlaender’s FPT‐algorithm to find (nice) tree‐decompositions of G and of H in time f₁(k)·(|G|+|H|).
   – Then do...

Excellent question. This is a classic problem in parameterized complexity that sits at the intersection of structural graph theory and logic.

The short answer is: The problem is W[1]-hard, parameterized by .

Let's break down why this is the case, building on the results you've already found.

The XP Upper Bound

You correctly found the result...

Let

 p–HOM(Τk , Τk ) = {(G , H , k) | tw(G) ≤ k , tw(H) ≤ k , there is a graph–homomorphism h : G → H }

and take k to be the parameter.
We show that p–HOM(Τk , Τk ) is fixed–parameter tractable (FPT).
In fact one can decide the existence of the homomorphism in

 f(k) · (|V(G)| + |V(H)|)ᴼ(1) time,

with f(k) = (k+1)^{(k+1)²}.
Thus the problem is in FPT and (unless FPT = W[1]) it ...

<think> We are considering the problem Hom(𝒯_k, 𝒯_k) parameterized by k, where 𝒯_k is the class of graphs with treewidth at most k. The question is whether this problem is fixed-parameter tractable (FPT) or W[1]-hard.

Recall that FPT means that the problem can be solved in time f(k) * poly(n) for some computable function f, where n is the input size.

From the provided references and known res...

The problem

p -HOM(𝒯k ,𝒯k )
Input : two graphs G,H with tw(G)≤k and tw(H)≤k
Parameter : k
Question : is there a homomorphism h : V(G)→V(H) ?

is fixed-parameter tractable. A simple dynamic–programming procedure that works simultaneously on tree–decompositions of G and H gives a running time of the form

  f(k)·(|V(G)|+|V(H)|)O(1) ,

hence FPT. Below is a concrete algorithm and a sho...

Complexity of the Homomorphism Problem Parameterized by Treewidth

This question asks about the parameterized complexity of the graph homomorphism problem where both the source and target graphs have bounded treewidth.

Analysis of the Problem

The homomorphism problem asks: given graphs and , both with treewidth at most , does there exist ...

This is an excellent question about the parameterized complexity of the graph homomorphism problem when both the source and target graphs have bounded treewidth.

The Answer

The problem parameterized by is W[1]-hard.

Key Results

The W[1]-hardness was established by Marx in his paper "Can You Beat Treewidth?" (FOCS 2007, Theory of Computin...