2014/03/25 by Johnson, Matthew, Kratsch, Dieter, Kratsch, Stefan +2
#Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1403.6347
The k-colouring reconfiguration 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 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 ≥ 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.