On the complexity of restoring corrupted colorings
Marzio De Biasi, Juho Lauri · RePEc: Research Papers in Economics
Abstract In the $$r$$ r -Fix problem, we are given a graph G, a (non-proper) vertex-coloring $$c : V(G) \rightarrow [r]$$ c : V ( G ) → [ r ] , and a positive integer k. The goal is to decide whether a proper r-coloring $$c'$$ c ′ is obtainable from c by recoloring at most k vertices of G. Recently, Junosza-Szaniawski et al. (in: SOFSEM 2015: theory and practice of computer science, Springer, Berlin, 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 \ge 3$$ r ≥ 3 , the problem $$r$$ r -Fix does not admit a polynomial kernel unless . Independently of their work, we give an alternative proof of the theorem. Furthermore, we study the complexity of $$r$$ r -Swap, where the only difference from $$r$$ r -Fix is that instead of k recolorings we have a budget of k color swaps. We show that for every $$r \ge 3$$ r ≥ 3 , the problem $$r$$ r -Swap is -hard whereas $$r$$ r -Fix is known to be FPT. Moreover, when r is part of the input, we observe both Fix and Swap are -hard parameterized by the treewidth of the input graph. We also study promise variants of the problems, where we are guaranteed that a proper r-coloring $$c'$$ c ′ is indeed obtainable from c by some finite number of swaps. For instance, we prove that for $$r=3$$ r = 3 , the problems $$r$$ r -Fix-Promise and $$r$$ r -Swap-Promise are -hard for planar graphs. As a consequence of our reduction, the problems cannot be solved in $$2^{o(\sqrt{n})}$$ 2 o ( n ) time unless the Exponential Time Hypothesis fails.