Fixing improper colorings of graphs

Valentin Garnero , Konstanty Junosza-Szaniawski , Mathieu Liedloff , Pedro Montealegre , Paweł Rzążewski

Abstract

We consider a variation of a recoloring problem, called the Color-Fixing. Let us have some non-proper r-coloring φ of a graph G. We investigate the problem of finding a proper r-coloring of G, which is “the most similar” to φ, i.e., the number k of vertices that have to be recolored is minimum possible. We observe that the problem is NP-complete for any fixed r>=3, even for bipartite planar graphs. Moreover, it is W[1]-hard even for bipartite graphs, when parameterized by the number k of allowed recoloring transformations. On the other hand, the problem is fixed-parameter tractable, when parameterized by k and the number r of colors. We provide a O*(2^n) algorithm for the problem and a linear algorithm for graphs with bounded treewidth. We also show several lower complexity bounds, using standard complexity assumptions. Finally, we investigate the fixing number of a graph G. It is the minimum k such that k recoloring transformations are sufficient to transform any coloring of G into a proper one.
Author Valentin Garnero
Valentin Garnero,,
-
, Konstanty Junosza-Szaniawski (FMIS / DAC)
Konstanty Junosza-Szaniawski,,
- Department of Algebra and Combinatorics
, Mathieu Liedloff
Mathieu Liedloff,,
-
, Pedro Montealegre
Pedro Montealegre,,
-
, Paweł Rzążewski (FMIS / DIPS)
Paweł Rzążewski,,
- Department of Information Processing Systems
Journal seriesTheoretical Computer Science, ISSN 0304-3975, (A 20 pkt)
Issue year2018
Vol711
Pages66-78
Publication size in sheets0.3
Keywords in Polishniepoprawne kolorowania, rekonfiguracja, złożoność obliczeniowa
Keywords in EnglishFixing number, Reconfiguration, Parameterized complexity
Abstract in PolishW pracy badamy wariant problemu kolorowania grafów, w którym dany jest graf wraz z pewnym jego pokolorowaniem, a zadanie polega na znalezieniu jemu “najbliższego” poprawnego kolorowania. Czyli ile wierzchołków należy najmniej przekolorować aby otrzymać poprawne kolorowanie. Pokazujemy, że problem jest NP-zupełny dla dowolnego ustalonego r>=3, nawet dla dwudzielnych grafów planarnych. Ponadto jest W[1]-trudny nawet dla grafów dwudzielnych, gdy w wersji parametryzowanej liczbą dozwolonych przekolorowań. Z drugiej strony jest on FPT dla parametryzacji przez liczbę przekolorowań. Przedstawiamy algorytm o złożoności O*(2^n) dla ogólnych grafów oraz liniowy algorytm dla grafów o ograniczonej szerokości drzewowej.
DOIDOI:10.1016/j.tcs.2017.11.013
URL http://www.sciencedirect.com/science/article/pii/S0304397517308435
Languageen angielski
Score (nominal)20
ScoreMinisterial score = 20.0, 17-07-2018, ArticleFromJournal
Ministerial score (2013-2016) = 20.0, 17-07-2018, ArticleFromJournal
Publication indicators WoS Impact Factor: 2016 = 0.698 (2) - 2016=0.815 (5)
Citation count*
Cite
Share Share

Get link to the record


* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Back