Document Open Access Logo

Parameterized Complexity of the List Coloring Reconfiguration Problem with Graph Parameters

Authors Tatsuhiko Hatanaka, Takehiro Ito, Xiao Zhou

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2017.51.pdf
  • Filesize: 2.6 MB
  • 13 pages

Document Identifiers

Author Details

Tatsuhiko Hatanaka
Takehiro Ito
Xiao Zhou

Cite As Get BibTex

Tatsuhiko Hatanaka, Takehiro Ito, and Xiao Zhou. Parameterized Complexity of the List Coloring Reconfiguration Problem with Graph Parameters. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 51:1-51:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.MFCS.2017.51

Abstract

Let G be a graph such that each vertex has its list of available colors, and assume that each list is a subset of the common set consisting of k colors. For two given list colorings of G, we study the problem of transforming one into the other by changing only one vertex color assignment at a time, while at all times maintaining a list coloring. This problem is known to be PSPACE-complete even for bounded bandwidth graphs and a fixed constant k. In this paper, we study the fixed-parameter tractability of the problem when parameterized by several graph parameters. We first give a fixed-parameter algorithm for the problem when parameterized by k and the modular-width of an input graph. We next give a fixed-parameter algorithm for the shortest variant which computes the length of a shortest transformation when parameterized by k and the size of a minimum vertex cover of an input graph. As corollaries, we show that the problem for cographs and the shortest variant for split graphs are fixed-parameter tractable even when only k is taken as a parameter. On the other hand, we prove that the problem is W[1]-hard when parameterized only by the size of a minimum vertex cover of an input graph.

Subject Classification

Keywords
  • combinatorial reconfiguration
  • fixed-parameter tractability
  • graph algorithm
  • list coloring
  • W[1]-hardness

Metrics

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

References

  1. Marthe Bonamy and Nicolas Bousquet. Recoloring bounded treewidth graphs. Electronic Notes in Discrete Mathematics, 44:257-262, 2013. URL: http://dx.doi.org/10.1016/j.endm.2013.10.040.
  2. Marthe Bonamy, Matthew Johnson, Ioannis Lignos, Viresh Patel, and Daniël Paulusma. Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs. Journal of Combinatorial Optimization, 27(1):132-143, 2014. URL: http://dx.doi.org/10.1007/s10878-012-9490-y.
  3. Paul Bonsma and Luis Cereceda. Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances. Theoretical Computer Science, 410(50):5215-5226, 2009. URL: http://dx.doi.org/10.1016/j.tcs.2009.08.023.
  4. Paul Bonsma, Amer E. Mouawad, Naomi Nishimura, and Venkatesh Raman. The complexity of bounded length graph recoloring and CSP reconfiguration. In Parameterized and Exact Computation - 9th International Symposium, IPEC 2014, Wroclaw, Poland, September 10-12, 2014. Revised Selected Papers, pages 110-121, 2014. URL: http://dx.doi.org/10.1007/978-3-319-13524-3_10.
  5. Richard C. Brewster, Sean McGuinness, Benjamin Moore, and Jonathan A. Noel. A dichotomy theorem for circular colouring reconfiguration. Theoretical Computer Science, 639:1-13, 2016. URL: http://dx.doi.org/10.1016/j.tcs.2016.05.015.
  6. Luis Cereceda. Mixing Graph Colourings. PhD thesis, The London School of Economics and Political Science, 2007. Google Scholar
  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. Rodney G. Downey and Michael R. Fellows. Parameterized Complexity. Springer-Verlag, 1999. Google Scholar
  9. Martin Dyer, Abraham D. Flaxman, Alan M. Frieze, and Eric Vigoda. Randomly coloring sparse random graphs with fewer colors than the maximum degree. Random Structures &Algorithms, 29(4):450-465, 2006. URL: http://dx.doi.org/10.1002/rsa.20129.
  10. Jakub Gajarský, Michael Lampis, and Sebastian Ordyniak. Parameterized algorithms for modular-width. In Parameterized and Exact Computation - 8th International Symposium, IPEC 2013, Sophia Antipolis, France, September 4-6, 2013, Revised Selected Papers, pages 163-176, 2013. URL: http://dx.doi.org/10.1007/978-3-319-03898-8_15.
  11. Tibor Gallai. Transitiv orientierbare graphen. Acta Mathematica Academiae Scientiarum Hungarica, 18(1):25-66, 1967. URL: http://dx.doi.org/10.1007/BF02020961.
  12. Michel Habib and Christophe Paul. A survey of the algorithmic aspects of modular decomposition. Computer Science Review, 4(1):41-59, 2010. URL: http://dx.doi.org/10.1016/j.cosrev.2010.01.001.
  13. 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, E98.A(6):1168-1178, 2015. URL: http://dx.doi.org/10.1587/transfun.E98.A.1168.
  14. 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. Theoretical Computer Science, 412(12):1054-1065, 2011. URL: http://dx.doi.org/10.1016/j.tcs.2010.12.005.
  15. 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.
  16. Sampath Kannan, Moni Naor, and Steven Rudich. Implicat representation of graphs. SIAM Journal on Discrete Mathematics, 5(4):596-603, 1992. URL: http://dx.doi.org/10.1137/0405049.
  17. Ross M. McConnell and Fabien de Montgolfier. Linear-time modular decomposition of directed graphs. Discrete Applied Mathematics, 145(2):198-209, 2005. URL: http://dx.doi.org/10.1016/j.dam.2004.02.017.
  18. Jan van den Heuvel. The complexity of change. In Surveys in Combinatorics 2013, pages 127-160. 2013. URL: http://dx.doi.org/10.1017/CBO9781139506748.005.
  19. Marcin Wrochna. Reconfiguration in bounded bandwidth and treedepth. CoRR, abs/1405.0847, 2014. Google Scholar
  20. Marcin Wrochna. Homomorphism reconfiguration via homotopy. In 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015, March 4-7, 2015, Garching, Germany, pages 730-742, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2015.730.
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact