Decremental optimization of vertex-coloring under the reconfiguration framework. (English) Zbl 07670476
Chen, Chi-Yeh (ed.) et al., Computing and combinatorics. 27th international conference, COCOON 2021, Tainan, Taiwan, October 24–26, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13025, 355-366 (2021).
Summary: Suppose that we are given a positive integer \(k\), and a \(k\)-(vertex-)coloring \(f_0\) of a given graph \(G\). Then we are asked to find a coloring of \(G\) using the minimum number of colors among colorings that are reachable from \(f_0\) by iteratively changing a color assignment of exactly one vertex while maintaining the property of \(k\)-colorings. In this paper, we give linear-time algorithms to solve the problem for graphs of degeneracy at most two and for the case where \(k \le 3\). These results imply linear-time algorithms for series-parallel graphs and grid graphs. In addition, we give linear-time algorithms for chordal graphs and cographs. On the other hand, we show that, for any \(k \ge 4\), this problem remains NP-hard for planar graphs with degeneracy three and maximum degree four. Thus, we obtain a complexity dichotomy for this problem with respect to degeneracy of a graph and the number \(k\) of colors.
For the entire collection see [Zbl 1507.68026].
For the entire collection see [Zbl 1507.68026].
MSC:
| 68Rxx | Discrete mathematics in relation to computer science |
References:
| [1] | Blanché, A.; Mizuta, H.; Ouvrard, P.; Suzuki, A.; Gąsieniec, L.; Klasing, R.; Radzik, T., Decremental optimization of dominating sets under the reconfiguration framework, Combinatorial Algorithms, 69-82 (2020), Cham: Springer, Cham · Zbl 07600999 · doi:10.1007/978-3-030-48966-3_6 |
| [2] | Bonamy, M.; Bousquet, N., Recoloring graphs via tree decompositions, Eur. J. Comb., 69, 200-213 (2018) · Zbl 1376.05048 · doi:10.1016/j.ejc.2017.10.010 |
| [3] | Bonamy, M.; Johnson, M.; Lignos, I.; Patel, V.; Paulusma, D., Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs, J. Comb. Optim., 27, 132-143 (2014) · Zbl 1284.05089 · doi:10.1007/s10878-012-9490-y |
| [4] | Bonsma, PS; Cereceda, L., Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances, Theoret. Comput. Sci., 410, 50, 5215-5226 (2009) · Zbl 1177.05112 · doi:10.1016/j.tcs.2009.08.023 |
| [5] | Bonsma, P.; Mouawad, AE; Nishimura, N.; Raman, V.; Cygan, M.; Heggernes, P., The complexity of bounded length graph recoloring and CSP reconfiguration, Parameterized and Exact Computation, 110-121 (2014), Cham: Springer, Cham · Zbl 1456.68065 · doi:10.1007/978-3-319-13524-3_10 |
| [6] | Bonsma, PS; Paulusma, D., Using contracted solution graphs for solving reconfiguration problems, Acta Informatica, 56, 619-648 (2019) · Zbl 1431.90161 · doi:10.1007/s00236-019-00336-8 |
| [7] | Cereceda, L., van den Heuvel, J., Johnson, M.: Connectedness of the graph of vertex-colourings. Discret. Math. 308(5), 913-919 (2008) · Zbl 1133.05053 |
| [8] | Cereceda, L., van den Heuvel, J., Johnson, M.: Finding paths between 3-colourings. J. Graph Theory 67(1), 69-82 (2011) · Zbl 1216.05154 |
| [9] | Christen, CA; Selkow, SM, Some perfect coloring properties of graphs, J. Comb. Theory Ser. B, 27, 1, 49-59 (1979) · Zbl 0427.05033 · doi:10.1016/0095-8956(79)90067-4 |
| [10] | Erickson, J.: Algorithms (2019) |
| [11] | Feghali, C.; Johnson, M.; Paulusma, D., A reconfigurations analogue of brooks’ theorem and its consequences, J. Graph Theory, 83, 4, 340-358 (2016) · Zbl 1350.05034 · doi:10.1002/jgt.22000 |
| [12] | Garey, MR; Johnson, DS, Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), San Francisco: Freeman, San Francisco · Zbl 0411.68039 |
| [13] | Hatanaka, T., Ito, T., Zhou, X.: The coloring reconfiguration problem on specific graph classes. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. E102.D(3), 423-429 (2019) |
| [14] | van den Heuvel, J.: The complexity of change. In: Blackburn, S.R., Gerke, S., Wildon, M. (eds.) Surveys in Combinatorics. London Mathematical Society Lecture Note Series, vol. 409, pp. 127-160. Cambridge University Press (2013) · Zbl 1307.05005 |
| [15] | Ito, T., On the complexity of reconfiguration problems, Theoret. Comput. Sci., 412, 12, 1054-1065 (2011) · Zbl 1207.68166 · doi:10.1016/j.tcs.2010.12.005 |
| [16] | Ito, T.; Mizuta, H.; Nishimura, N.; Suzuki, A.; Du, D-Z; Duan, Z.; Tian, C., Incremental optimization of independent sets under the reconfiguration framework, Computing and Combinatorics, 313-324 (2019), Cham: Springer, Cham · Zbl 1534.68174 · doi:10.1007/978-3-030-26176-4_26 |
| [17] | Ito, T., Mizuta, H., Nishimura, N., Suzuki, A.: Incremental optimization of independent sets under the reconfiguration framework. J. Comb. Optim. 1-16 (2020). doi:10.1007/s10878-020-00630-z |
| [18] | Johnson, M.; Kratsch, D.; Kratsch, S.; Patel, V.; Paulusma, D., Finding shortest paths between graph colourings, Algorithmica, 75, 295-321 (2016) · Zbl 1350.68148 · doi:10.1007/s00453-015-0009-7 |
| [19] | Karp, RM; Miller, RE; Thatcher, JW; Bohlinger, JD, Reducibility among combinatorial problems, Complexity of Computer Computations, 85-103 (1972), Boston: Springer, Boston · Zbl 1467.68065 · doi:10.1007/978-1-4684-2001-2_9 |
| [20] | Markossian, SE; Gasparian, GS; Reed, BA, \( \beta \)-perfect graphs, J. Comb. Theory Ser. B, 67, 1, 1-11 (1996) · Zbl 0857.05038 · doi:10.1006/jctb.1996.0030 |
| [21] | Mynhardt, C.M., Nasserasr, S.: Reconfiguration of colourings and dominating sets in graphs. In: 50 Years of Combinatorics, Graph Theory, and Computing, pp. 171-191. Chapman and Hall/CRC (2019) · Zbl 1451.05118 |
| [22] | Nishimura, N., Introduction to reconfiguration, Algorithms, 11, 4, 52 (2018) · Zbl 1461.68164 · doi:10.3390/a11040052 |
| [23] | Rose, DJ; Tarjan, RE; Lueker, GS, Algorithmic aspects of vertex elimination on graphs, SIAM J. Comput., 5, 2, 266-283 (1976) · Zbl 0353.65019 · doi:10.1137/0205021 |
| [24] | Wrochna, M., Reconfiguration in bounded bandwidth and tree-depth, J. Comput. Syst. Sci., 93, 1-10 (2018) · Zbl 1382.68183 · doi:10.1016/j.jcss.2017.11.003 |
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.
