TUTCRIS - Tampereen teknillinen yliopisto

TUTCRIS

On the complexity of restoring corrupted colorings

Tutkimustuotosvertaisarvioitu

Standard

On the complexity of restoring corrupted colorings. / De Biasi, Marzio; Lauri, Juho.

julkaisussa: Journal of Combinatorial Optimization, Vuosikerta 37, Nro 4, 05.2019, s. 1150-1169.

Tutkimustuotosvertaisarvioitu

Harvard

De Biasi, M & Lauri, J 2019, 'On the complexity of restoring corrupted colorings', Journal of Combinatorial Optimization, Vuosikerta. 37, Nro 4, Sivut 1150-1169. https://doi.org/10.1007/s10878-018-0342-2

APA

De Biasi, M., & Lauri, J. (2019). On the complexity of restoring corrupted colorings. Journal of Combinatorial Optimization, 37(4), 1150-1169. https://doi.org/10.1007/s10878-018-0342-2

Vancouver

De Biasi M, Lauri J. On the complexity of restoring corrupted colorings. Journal of Combinatorial Optimization. 2019 touko;37(4):1150-1169. https://doi.org/10.1007/s10878-018-0342-2

Author

De Biasi, Marzio ; Lauri, Juho. / On the complexity of restoring corrupted colorings. Julkaisussa: Journal of Combinatorial Optimization. 2019 ; Vuosikerta 37, Nro 4. Sivut 1150-1169.

Bibtex - Lataa

@article{75d21b2bafb645529e9f03e6eb77406e,
title = "On the complexity of restoring corrupted colorings",
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.",
keywords = "Combinatorial reconfiguration, Computational complexity, Graph coloring, Local search, Parameterized complexity",
author = "{De Biasi}, Marzio and Juho Lauri",
year = "2019",
month = "5",
doi = "10.1007/s10878-018-0342-2",
language = "English",
volume = "37",
pages = "1150--1169",
journal = "Journal of Combinatorial Optimization",
issn = "1382-6905",
publisher = "Springer Verlag",
number = "4",

}

RIS (suitable for import to EndNote) - Lataa

TY - JOUR

T1 - On the complexity of restoring corrupted colorings

AU - De Biasi, Marzio

AU - Lauri, Juho

PY - 2019/5

Y1 - 2019/5

N2 - 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.

AB - 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.

KW - Combinatorial reconfiguration

KW - Computational complexity

KW - Graph coloring

KW - Local search

KW - Parameterized complexity

U2 - 10.1007/s10878-018-0342-2

DO - 10.1007/s10878-018-0342-2

M3 - Article

VL - 37

SP - 1150

EP - 1169

JO - Journal of Combinatorial Optimization

JF - Journal of Combinatorial Optimization

SN - 1382-6905

IS - 4

ER -