Title | ||
---|---|---|
Finding Paths between graph colourings: PSPACE-completeness and superpolynomial distances |
Abstract | ||
---|---|---|
Suppose we are given a graph G together with two proper vertex k-colourings of G, @a and @b. How easily can we decide whether it is possible to transform @a into @b by 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 k in (i) and (ii) are tight, in the sense that for larger values of k, it is always possible to recolour @a to @b. We also exhibit, for every k=4, a class of graphs {G"N","k:N@?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 @W(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. |
Year | DOI | Venue |
---|---|---|
2007 | 10.1016/j.tcs.2009.08.023 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
vertex-recolouring,colour graph,pspace-complete,superpolynomial dis- tance. | Conference | 410 |
Issue | ISSN | ISBN |
50 | Theoretical Computer Science | 3-540-74455-X |
Citations | PageRank | References |
58 | 3.74 | 7 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Paul Bonsma | 1 | 287 | 20.46 |
Luis Cereceda | 2 | 156 | 10.77 |