Finding Shortest Paths Between Graph Colourings

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