Fixing improper colorings of graphs. (English) Zbl 1386.68069
Summary: In this paper we consider a variation of a recoloring problem, called the Color-Fixing. Let us have some non-proper \(r\)-coloring \(\phi\) of a graph \(G\). We investigate the problem of finding a proper \(r\)-coloring of \(G\), which is “the most similar” to \(\phi\), 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\geq3\), 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 \(2^n\cdot n^{\mathcal{O}(1)}\) 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.
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
| 05C15 | Coloring of graphs and hypergraphs |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
References:
| [1] | Ausiello, G.; Escoffier, B.; Monnot, J.; Paschos, V. Th., Reoptimization of minimum and maximum traveling salesman’s tours, J. Discrete Algorithms, 7, 453-463 (2009) · Zbl 1180.90259 |
| [2] | Bilò, D.; Böckenhauer, H.-J.; Komm, D.; Královic, R.; Mömke, T.; Seibert, S.; Zych, A., Reoptimization of the shortest common superstring problem, Algorithmica, 61, 227-251 (2011) · Zbl 1238.68189 |
| [3] | Björklund, A.; Husfeldt, T.; Koivisto, M., Set partitioning via inclusion-exclusion, SIAM J. Comput., 39, 546-563 (2009) · Zbl 1215.05056 |
| [4] | Bodlaender, H.; Jansen, B.; Kratsch, S., Cross-composition: a new technique for kernelization lower bounds, (Proc. of STACS 2011. Proc. of STACS 2011, LIPIcs. Leibniz Int. Proc. Inform., vol. 9 (2011)), 165-176 · Zbl 1230.68085 |
| [5] | Bodlaender, H.; Koster, A., Combinatorial optimization on graphs of bounded treewidth, Comput J., 308, 255-269 (2008) |
| [6] | Bonamy, M.; Bousquet, N., Recoloring bounded treewidth graphs, Electron. Notes Discrete Math., 44, 257-262 (2013) |
| [7] | Bonsma, P.; Cereceda, L., Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances, (Proc. of MFCS 2007. Proc. of MFCS 2007, Lecture Notes in Comput. Sci., vol. 4708 (2007)), 738-749 · Zbl 1147.68529 |
| [8] | Cereceda, L.; van den Heuvel, J.; Johnson, M., Mixing 3-colourings in bipartite graphs, (Proc. of WG 2007. Proc. of WG 2007, Lecture Notes in Comput. Sci., vol. 4769 (2007)), 166-177 · Zbl 1141.68521 |
| [9] | Cereceda, L.; van den Heuvel, J.; Johnson, M., Connectedness of the graph of vertex colourings, Discrete Math., 308, 166-177 (2008) · Zbl 1133.05053 |
| [10] | Cereceda, L.; van den Heuvel, J.; Johnson, M., Finding paths between 3-colorings, J. Graph Theory, 67, 69-82 (2011) · Zbl 1216.05154 |
| [11] | Cygan, M.; Fomin, F.; Kowalik, Ł.; Lokshtanov, D.; Marx, D.; Pilipczuk, M.; Pilipczuk, M.; Saurabh, S., Parameterized Algorithms (2015), Springer · Zbl 1334.90001 |
| [12] | Diestel, R., Graph Theory, Grad. Texts in Math. (2005), Springer · Zbl 1074.05001 |
| [13] | Downey, R. G.; Fellows, M. R., Parameterized Complexity, Monogr. Comput. Sci. (1999), Springer · Zbl 0914.68076 |
| [14] | Felsner, S.; Huemer, C.; Saumell, M., Recoloring directed graphs, (Proc. of XIII Encuentros de Geometría Computacional (2009)), 91-97 |
| [15] | Impagliazzo, R.; Paturi, R., On the complexity of \(k\)-SAT, J. Comput. System Sci., 62, 367-375 (2001) · Zbl 0990.68079 |
| [16] | Impagliazzo, R.; Paturi, R.; Zane, F., Which problems have strongly exponential complexity?, J. Comput. System Sci., 63, 512-530 (2001) · Zbl 1006.68052 |
| [17] | Ito, T.; Demaine, E.; Harvey, N. J.A.; Papadimitrious, C. H.; Sideri, M.; Uehara, R.; Uno, Y., On the complexity of reconfiguration problems, Theoret. Comput. Sci., 412, 1054-1065 (2011) · Zbl 1207.68166 |
| [18] | Jerrum, M., A very simple algorithm for estimating the number of \(k\)-colorings of a low-degree graph, Random Structures Algorithms, 7, 157-165 (1995) · Zbl 0833.60070 |
| [19] | Junosza-Szaniawski, K.; Liedloff, M.; Rzążewski, P., Fixing improper colorings of graphs, (Proc. of SOFSEM 2015. Proc. of SOFSEM 2015, Lecture Notes in Comput. Sci., vol. 8939 (2015)), 266-276 · Zbl 1386.68072 |
| [20] | Kratochvíl, J., Precoloring extension with fixed color bound, Acta Math. Univ. Comenian. (N.S.) (1993) · Zbl 0821.05027 |
| [21] | Lokshtanov, D.; Marx, D.; Saurabh, S., Known algorithms on graphs of bounded treewidth are probably optimal, (Proc. of SODA 2011 (2011), SIAM), 760-776 · Zbl 1373.68242 |
| [22] | Lokshtanov, D.; Marx, D.; Saurabh, S., Lower bounds based on the exponential time hypothesis, Bull. Eur. Assoc. Theor. Comput. Sci. EATCS, 105, 41-72 (2011) · Zbl 1258.68068 |
| [23] | Marx, D., Can you beat treewidth?, Theory Comput., 6, 85-112 (2010) · Zbl 1213.68316 |
| [24] | Marx, D.; Pilipczuk, M., Optimal parameterized algorithms for planar facility location problems using Voronoi diagrams, CoRR · Zbl 1422.68253 |
| [25] | Shachnai, H.; Tamir, G.; Tamir, T., A theory and algorithms for combinatorial reoptimization, (Proc. of LATIN 2012. Proc. of LATIN 2012, Lecture Notes in Comput. Sci., vol. 7256 (2012)), 618-630 · Zbl 1354.90115 |
| [26] | Zych, A.; Bilò, D., New reoptimization techniques applied to Steiner tree problem, Electron. Notes Discrete Math., 37, 387-392 (2001) · Zbl 1268.90073 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
