Abstract

In this paper, we study the All-Colors problem: given a graph $G$ each of whose vertices is equipped with a button and assigned a color value from the set ${0,1, \dots, m-1}$ and an integer $k$, can we reach color value $1 \bmod m$ on every vertex of $G$ by pressing the button at most $k$ times. The rule we follow is the following: if a button of a corresponding vertex is pressed one time, then the color values of the vertex and its neighbors are incremented by 1. This problem is known to be NP-hard on bipartite graphs even when $m = 2$ [Theor.~Comput.~Sci., 2007], although linear time solvable on trees [SIAM J.~Comput., 2004]. In this work, we study this problem in the realm of parameterized complexity with respect to several parameters. In particular, we show the followings for All-Colors. W[1]-hard when parameterized by solution size $k$. FPT algorithm parameterized by solution size + maximum degree. FPT algorithm parameterized by treewidth or clique-width. NP-hard on sub-cubic planar graphs.