Ruling out FPT algorithms for Weighted Coloring on forests

The objective of this article is to provide hardness results for computing σ(G,w) and σ(G,w;r) when G is a tree or a forest, relying on complexity assumptions weaker than the ETH. Namely, we study the problem from the viewpoint of parameterized complexity, and we assume the weaker hypothesis FPT≠W[1]. Building on the techniques of Araújo et al., we prove that when G is a forest, the decision problem of computing σ(G,w) is W[1]-hard parameterized by the size of a largest connected component of G, and that computing σ(G,w;r) is W[2]-hard parameterized by r. Our results rule out the existence of FPT algorithms for computing these invariants on trees or forests for many natural choices of the parameter.