Finding Shortest Paths Between Graph Colourings

Johnson, M.; Kratsch, D.; Kratsch, S.; Patel, V.; Paulusma, D.

Abstract

The k-colouring reconguration problem asks whether, for a given graph G, two proper k-colourings and of G, and a positive integer `, there exists a sequence of at most ` + 1 proper k-colourings of G which starts with and ends with and where successive colourings in the sequence dier on exactly one vertex of G. We give a complete picture of the parameterized complexity of the k-colouring reconguration problem for each xed k when parameterized by `. First we show that the k-colouring reconguration problem is polynomial-time solvable for k = 3, settling an open problem of Cereceda, van den Heuvel and Johnson. Then, for all k 4, we show that the k-colouring reconguration problem, when parameterized by `, is xed-parameter tractable (addressing a question of Mouawad, Nishimura, Raman, Simjour and Suzuki) but that it has no polynomial kernel unless the polynomial hierarchy collapses.

Citation

Johnson, M., Kratsch, D., Kratsch, S., Patel, V., & Paulusma, D. (2016). Finding Shortest Paths Between Graph Colourings. Algorithmica, 75(2), 295-321. https://doi.org/10.1007/s00453-015-0009-7

• Journal Article Type: Article
• Acceptance Date: Apr 30, 2015
• Online Publication Date: May 12, 2015
• Publication Date: Jun 1, 2016
• Deposit Date: May 25, 2015
• Publicly Available Date: May 12, 2016
• Journal: Algorithmica
• Print ISSN: 0178-4617
• Electronic ISSN: 1432-0541
• Publisher: Springer
• Peer Reviewed: Peer Reviewed
• Volume: 75
• Issue: 2
• Pages: 295-321
• DOI: https://doi.org/10.1007/s00453-015-0009-7
• Keywords: Graph colouring, Graph algorithms, Reconfigurations, Reconfiguration graphs, Fixed parameter tractability.
• Public URL: https://durham-repository.worktribe.com/output/1407581