Ruling out FPT algorithms for Weighted Coloring on forests

Abstract

Given a graph $G$, a proper $k$-coloring of $G$ is a partition $c=(S_i{)}_{i\in [1,k]}$ of $V(G)$ into $k$ stable sets $S_1,\dots ,S_k$. Given a weight function $w:V(G)\to {\mathbb{R}}^{+}$, the weight of a color $S_i$ is defined as $w(i)={\max }_{v\in S_i}w(v)$ and the weight of a coloring $c$ as $w(c)={\sum }_{i=1}^{k}w(i)$. Guan and Zhu [Inf. Process. Lett., 1997] defined the weighted chromatic number of a pair $(G,w)$, denoted by $\sigma (G,w)$, as the minimum weight of a proper coloring of $G$. For a positive integer $r$, they also defined $\sigma (G,w;r)$ as the minimum of $w(c)$ among all proper $r$-colorings $c$ of $G$. The complexity of determining $\sigma (G,w)$ when $G$ is a tree was open for almost 20 years, until Araújo et al. [SIAM J. Discrete Math., 2014] recently proved that the problem cannot be solved in time $n^{o(\log n)}$ on $n$-vertex trees unless the Exponential Time Hypothesis (ETH) fails. The objective of this article is to provide hardness results for computing $\sigma (G,w)$ and $\sigma (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\ne W[1]$. Building on the techniques of Araújo et al., we prove that when $G$ is a forest, computing $\sigma (G,w)$ is $W[1]$-hard parameterized by the size of a largest connected component of $G$, and that computing $\sigma (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.

14 pages, 4 figures