Abstract
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.
A. Suzuki—Partially supported by JSPS KAKENHI Grant Numbers JP18H04091, JP20K11666 and JP20H05794, Japan.
X. Zhou—Partially supported by JSPS KAKENHI Grant Number JP19K11813, Japan.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Blanché, A., Mizuta, H., Ouvrard, P., Suzuki, A.: Decremental optimization of dominating sets under the reconfiguration framework. In: Gąsieniec, L., Klasing, R., Radzik, T. (eds.) IWOCA 2020. LNCS, vol. 12126, pp. 69–82. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-48966-3_6
Bonamy, M., Bousquet, N.: Recoloring graphs via tree decompositions. Eur. J. Comb. 69, 200–213 (2018)
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)
Bonsma, P.S., Cereceda, L.: Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances. Theoret. Comput. Sci. 410(50), 5215–5226 (2009)
Bonsma, P., Mouawad, A.E., Nishimura, N., Raman, V.: The complexity of bounded length graph recoloring and CSP reconfiguration. In: Cygan, M., Heggernes, P. (eds.) IPEC 2014. LNCS, vol. 8894, pp. 110–121. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-13524-3_10
Bonsma, P.S., Paulusma, D.: Using contracted solution graphs for solving reconfiguration problems. Acta Informatica 56, 619–648 (2019)
Cereceda, L., van den Heuvel, J., Johnson, M.: Connectedness of the graph of vertex-colourings. Discret. Math. 308(5), 913–919 (2008)
Cereceda, L., van den Heuvel, J., Johnson, M.: Finding paths between 3-colourings. J. Graph Theory 67(1), 69–82 (2011)
Christen, C.A., Selkow, S.M.: Some perfect coloring properties of graphs. J. Comb. Theory Ser. B 27(1), 49–59 (1979)
Erickson, J.: Algorithms (2019)
Feghali, C., Johnson, M., Paulusma, D.: A reconfigurations analogue of brooks’ theorem and its consequences. J. Graph Theory 83(4), 340–358 (2016)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco (1979)
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)
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)
Ito, T., et al.: On the complexity of reconfiguration problems. Theoret. Comput. Sci. 412(12), 1054–1065 (2011)
Ito, T., Mizuta, H., Nishimura, N., Suzuki, A.: Incremental optimization of independent sets under the reconfiguration framework. In: Du, D.-Z., Duan, Z., Tian, C. (eds.) COCOON 2019. LNCS, vol. 11653, pp. 313–324. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26176-4_26
Ito, T., Mizuta, H., Nishimura, N., Suzuki, A.: Incremental optimization of independent sets under the reconfiguration framework. J. Comb. Optim. 1–16 (2020). https://doi.org/10.1007/s10878-020-00630-z
Johnson, M., Kratsch, D., Kratsch, S., Patel, V., Paulusma, D.: Finding shortest paths between graph colourings. Algorithmica 75, 295–321 (2016)
Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W., Bohlinger, J.D. (eds.) Complexity of Computer Computations. The IBM Research Symposia Series, pp. 85–103. Springer, Boston (1972). https://doi.org/10.1007/978-1-4684-2001-2_9
Markossian, S.E., Gasparian, G.S., Reed, B.A.: \(\beta \)-perfect graphs. J. Comb. Theory Ser. B 67(1), 1–11 (1996)
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)
Nishimura, N.: Introduction to reconfiguration. Algorithms 11(4), 52 (2018)
Rose, D.J., Tarjan, R.E., Lueker, G.S.: Algorithmic aspects of vertex elimination on graphs. SIAM J. Comput. 5(2), 266–283 (1976)
Wrochna, M.: Reconfiguration in bounded bandwidth and tree-depth. J. Comput. Syst. Sci. 93, 1–10 (2018)
Acknowledgment
We are grateful to Tatsuhiko Hatanaka, Takehiro Ito and Haruka Mizuta for valuable discussions with them. We thank the anonymous referees for their constructive suggestions and comments.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Yanagisawa, Y., Suzuki, A., Tamura, Y., Zhou, X. (2021). Decremental Optimization of Vertex-Coloring Under the Reconfiguration Framework. In: Chen, CY., Hon, WK., Hung, LJ., Lee, CW. (eds) Computing and Combinatorics. COCOON 2021. Lecture Notes in Computer Science(), vol 13025. Springer, Cham. https://doi.org/10.1007/978-3-030-89543-3_30
Download citation
DOI: https://doi.org/10.1007/978-3-030-89543-3_30
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-89542-6
Online ISBN: 978-3-030-89543-3
eBook Packages: Computer ScienceComputer Science (R0)