Finding Paths between graph colourings: PSPACE-completeness and superpolynomial distances

Suppose we are given a graph G together with two proper vertex k-colourings of G, alpha and beta. How easily can we decide whether it is possible to transform alpha into beta recolouring vertices of G one at a time, making sure we always have a proper k-colouring of G? This decision problem is trivial for k = 2, and decidable in polynomial time for k = 3. Here we prove it is PSPACE-complete for all k >= 4. In particular, we prove that the problem remains PSPACE-complete for bipartite graphs, as well as for: (i) planar graphs and 4 <= k <= 6, and (ii) bipartite planar graphs and k = 4. Moreover, the values of kin (i) and (ii) are tight, in the sense that for larger values of k, it is always possible to recolour alpha to beta. We also exhibit, for every k >= 4, a class of graphs {G(N,k) : N is an element of N*}, together with two k-colourings for each G(N,k), such that the minimum number of recolouring steps required to transform the first colouring into the second is superpolynomial in the size of the graph: the minimum number of steps is Omega(2(N)), whereas the size of G(N) is O(N-2). This is in stark contrast to the k = 3 case, where it is known that the minimum number of recolouring steps is at most quadratic in the number of vertices. We also show that a class of bipartite graphs can be constructed with this property, and that: (i) for 4 <= k <= 6 planar graphs and (ii) for k = 4 bipartite planar graphs can be constructed with this property. This provides a remarkable correspondence between the tractability of the problem and its underlying structure. (C) 2009 Elsevier B.V. All rights reserved.