On the complexity of restoring corrupted colorings

Marzio Biasi and Juho Lauri ()
Additional contact information
Juho Lauri: Tampere University of Technology

Journal of Combinatorial Optimization, 2019, vol. 37, issue 4, No 4, 1150-1169

Abstract: 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.

Keywords: Graph coloring; Computational complexity; Parameterized complexity; Combinatorial reconfiguration; Local search (search for similar items in EconPapers)
Date: 2019
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-018-0342-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:37:y:2019:i:4:d:10.1007_s10878-018-0342-2

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-018-0342-2

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().