## On the complexity of restoring corrupted colorings

Research output: Contribution to journal › Article › Scientific › peer-review

### Details

Original language | English |
---|---|

Pages (from-to) | 1150-1169 |

Number of pages | 20 |

Journal | Journal of Combinatorial Optimization |

Volume | 37 |

Issue number | 4 |

DOIs | |

Publication status | Published - May 2019 |

Publication type | A1 Journal article-refereed |

### Abstract

In the r-Fix problem, we are given a graph G, a (non-proper) vertex-coloring c: V(G) → [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 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≥ 3 , the problem r-Fix does not admit a polynomial kernel unless [InlineEquation not available: see fulltext.]. Independently of their work, we give an alternative proof of the theorem. Furthermore, we study the complexity of r-Swap, where the only difference from r-Fix is that instead of k recolorings we have a budget of k color swaps. We show that for every r≥ 3 , the problem r-Swap is [InlineEquation not available: see fulltext.]-hard whereas r-Fix is known to be FPT. Moreover, when r is part of the input, we observe both Fix and Swap are [InlineEquation not available: see fulltext.]-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^{′} is indeed obtainable from c by some finite number of swaps. For instance, we prove that for r= 3 , the problems r-Fix-Promise and r-Swap-Promise are [InlineEquation not available: see fulltext.]-hard for planar graphs. As a consequence of our reduction, the problems cannot be solved in 2o(n) time unless the Exponential Time Hypothesis fails.

### ASJC Scopus subject areas

### Keywords

- Combinatorial reconfiguration, Computational complexity, Graph coloring, Local search, Parameterized complexity