On the Complexity of Restoring Corrupted Colorings

In the probrFix problem, we are given a graph $G$, a (non-proper) vertex-coloring $c : V(G) to [r]$, and a positive integer~$k$. The goal is to decide whether a proper $r$-coloring $c'$ is obtainable from~$c$ by recoloring at most $k$ vertices of $G$. Recently, Junosza-Szaniawski, Liedloff, and Rz{k{a}}{.z}ewski [SOFSEM 2015] asked whether the problem has a polynomial kernel parameterized by the number of recolorings~$k$. In a full version of the manuscript, the authors together with Garnero and Montealegre, answered the question in the negative: for every $r geq 3$, the problem probrFix does not admit a polynomial kernel unless $NP subseteq coNP / poly$. Independently of their work, we give an alternative proof of the theorem. Furthermore, we study the complexity of probrFixSwap, where the only difference from probrFix is that instead of~$k$ recolorings we have a budget of~$k$ color swaps. We show that for every $r geq 3$, the problem probrFixSwap is $W[1]$-hard whereas probrFix is known to be FPT. Moreover, when~$r$ is part of the input, we observe both probFix and probFixSwap are $W[1]$-hard parameterized by treewidth. We also study promise variants of the problems, where we are guaranteed that a proper $r$-coloring~$c'$ is indeed obtainable from~$c$ by some finite number of swaps. For instance, we prove that for $r=3$, the problems probrFixPromise and probrFixSwapPromise are $NP$-hard for planar graphs. As a consequence of our reduction, the problems cannot be solved in $2^{o(sqrt{n})}$ time unless the Exponential Time Hypothesis (ETH) fails.