Algorithms for Coloring Reconfiguration Under Recolorability Constraints

Authors Hiroki Osawa, Akira Suzuki , Takehiro Ito , Xiao Zhou



PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2018.37.pdf
  • Filesize: 0.98 MB
  • 13 pages

Document Identifiers

Author Details

Hiroki Osawa
  • Graduate School of Information Sciences, Tohoku University, Japan
Akira Suzuki
  • Graduate School of Information Sciences, Tohoku University, Japan
Takehiro Ito
  • Graduate School of Information Sciences, Tohoku University, Japan
Xiao Zhou
  • Graduate School of Information Sciences, Tohoku University, Japan

Cite AsGet BibTex

Hiroki Osawa, Akira Suzuki, Takehiro Ito, and Xiao Zhou. Algorithms for Coloring Reconfiguration Under Recolorability Constraints. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 37:1-37:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ISAAC.2018.37

Abstract

Coloring reconfiguration is one of the most well-studied reconfiguration problems. In the problem, we are given two (vertex-)colorings of a graph using at most k colors, and asked to determine whether there exists a transformation between them by recoloring only a single vertex at a time, while maintaining a k-coloring throughout. It is known that this problem is solvable in linear time for any graph if k <=3, while is PSPACE-complete for a fixed k >= 4. In this paper, we further investigate the problem from the viewpoint of recolorability constraints, which forbid some pairs of colors to be recolored directly. More specifically, the recolorability constraint is given in terms of an undirected graph R such that each node in R corresponds to a color, and each edge in R represents a pair of colors that can be recolored directly. In this paper, we give a linear-time algorithm to solve the problem under such a recolorability constraint if R is of maximum degree at most two. In addition, we show that the minimum number of recoloring steps required for a desired transformation can be computed in linear time for a yes-instance. We note that our results generalize the known positive ones for coloring reconfiguration.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
Keywords
  • combinatorial reconfiguration
  • graph algorithm
  • graph coloring

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Marthe Bonamy and Nicolas Bousquet. Recoloring graphs via tree decompositions. Eur. J. Comb., 69:200-213, 2018. URL: http://dx.doi.org/10.1016/j.ejc.2017.10.010.
  2. Marthe Bonamy, Matthew Johnson, Ioannis Lignos, Viresh Patel, and Daniël Paulusma. Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs. J. Comb. Optim., 27(1):132-143, 2014. URL: http://dx.doi.org/10.1007/s10878-012-9490-y.
  3. Paul S. Bonsma and Luis Cereceda. Finding Paths between graph colourings: PSPACE-completeness and superpolynomial distances. Theor. Comput. Sci., 410(50):5215-5226, 2009. URL: http://dx.doi.org/10.1016/j.tcs.2009.08.023.
  4. Paul S. Bonsma, Amer E. Mouawad, Naomi Nishimura, and Venkatesh Raman. The Complexity of Bounded Length Graph Recoloring and CSP Reconfiguration. In Marek Cygan and Pinar Heggernes, editors, Parameterized and Exact Computation - 9th International Symposium, IPEC 2014, Wroclaw, Poland, September 10-12, 2014. Revised Selected Papers, volume 8894 of Lecture Notes in Computer Science, pages 110-121. Springer, 2014. URL: http://dx.doi.org/10.1007/978-3-319-13524-3_10.
  5. Paul S. Bonsma and Daniël Paulusma. Using Contracted Solution Graphs for Solving Reconfiguration Problems. In Piotr Faliszewski, Anca Muscholl, and Rolf Niedermeier, editors, 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016, August 22-26, 2016 - Kraków, Poland, volume 58 of LIPIcs, pages 20:1-20:15. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.MFCS.2016.20.
  6. Richard C. Brewster, Sean McGuinness, Benjamin Moore, and Jonathan A. Noel. A dichotomy theorem for circular colouring reconfiguration. Theor. Comput. Sci., 639:1-13, 2016. URL: http://dx.doi.org/10.1016/j.tcs.2016.05.015.
  7. Luis Cereceda, Jan van den Heuvel, and Matthew Johnson. Finding paths between 3-colorings. Journal of Graph Theory, 67(1):69-82, 2011. URL: http://dx.doi.org/10.1002/jgt.20514.
  8. Tatsuhiko Hatanaka, Takehiro Ito, and Xiao Zhou. The List Coloring Reconfiguration Problem for Bounded Pathwidth Graphs. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 98-A(6):1168-1178, 2015. URL: http://search.ieice.org/bin/summary.php?id=e98-a_6_1168, URL: http://dx.doi.org/10.1587/transfun.E98.A.1168.
  9. Tatsuhiko Hatanaka, Takehiro Ito, and Xiao Zhou. Parameterized complexity of the list coloring reconfiguration problem with graph parameters. Theor. Comput. Sci., 739:65-79, 2018. URL: http://dx.doi.org/10.1016/j.tcs.2018.05.005.
  10. Jan van den Heuvel. The complexity of change. In Simon R. Blackburn, Stefanie Gerke, and Mark Wildon, editors, Surveys in Combinatorics 2013, volume 409 of London Mathematical Society Lecture Note Series, pages 127-160. Cambridge University Press, 2013. URL: http://dx.doi.org/10.1017/CBO9781139506748.005.
  11. Takehiro Ito, Erik D. Demaine, Nicholas J. A. Harvey, Christos H. Papadimitriou, Martha Sideri, Ryuhei Uehara, and Yushi Uno. On the complexity of reconfiguration problems. Theor. Comput. Sci., 412(12-14):1054-1065, 2011. URL: http://dx.doi.org/10.1016/j.tcs.2010.12.005.
  12. Matthew Johnson, Dieter Kratsch, Stefan Kratsch, Viresh Patel, and Daniël Paulusma. Finding Shortest Paths Between Graph Colourings. Algorithmica, 75(2):295-321, 2016. URL: http://dx.doi.org/10.1007/s00453-015-0009-7.
  13. Naomi Nishimura. Introduction to Reconfiguration. Algorithms, 11(4):52, 2018. URL: http://dx.doi.org/10.3390/a11040052.
  14. Hiroki Osawa, Akira Suzuki, Takehiro Ito, and Xiao Zhou. Complexity of Coloring Reconfiguration under Recolorability Constraints. In Yoshio Okamoto and Takeshi Tokuyama, editors, 28th International Symposium on Algorithms and Computation, ISAAC 2017, December 9-12, 2017, Phuket, Thailand, volume 92 of LIPIcs, pages 62:1-62:12. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.ISAAC.2017.62.
  15. Marcin Wrochna. Homomorphism Reconfiguration via Homotopy. In Ernst W. Mayr and Nicolas Ollinger, editors, 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015, March 4-7, 2015, Garching, Germany, volume 30 of LIPIcs, pages 730-742. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2015.730.
  16. Marcin Wrochna. Reconfiguration in bounded bandwidth and tree-depth. J. Comput. Syst. Sci., 93:1-10, 2018. URL: http://dx.doi.org/10.1016/j.jcss.2017.11.003.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail