A polynomially searchable exponential neighbourhood for graph colouring

Abstract

In this paper, we develop a new graph colouring strategy. Our heuristic is an example of a so-called polynomially searchable exponential neighbourhood approach. The neighbourhood is that of permutations of the colours of vertices of a subgraph. Our approach provides a solution method for colouring problems with edge weights. Results for initial tests on unweighted K-colouring benchmark problems are presented. Our colour permutation move was found in practice to be too slow to justify its use on these problems. By contrast, our implementation of iterative descent, which incorporates a permutation kickback move, performed extremely well. Moreover, our approach may yet prove valuable for weighted K-colouring. In addition, our approach offers an improved measure of the distance between colourings of a graph.

Appendix: Implementation details of vertex descent and permutation kickstarts

We implemented vertex descent efficiently by first computing a table giving the relative cost of colouring each vertex, i, to a particular colour, μ (with all other vertices left the same)

The ‘best colours’ for a vertex are those for which c(i, μ)⩽c(i, ν) for all ν. From our table we compute a colour list, L(i)s, of best colours for each vertex. To perform vertex descent for a vertex i, we choose one of the colours in the colour list L(i). When a vertex changes colour, we update the colour table for all its adjacent vertices and if necessary their colour lists. Keeping this information is efficient because, for any reasonable colouring, the vast majority of vertices have only one element in its list and so do not need to be updated. The overhead of computing the original cost table is reduced by performing many sweeps at a time.

The disruptive permutation move used in KickstartP is performed as follows. A subgraph is chosen randomly and the corresponding permutation matrix on colour classes constructed as for PermImprove. The minimum non-zero element in the matrix is then added to the (zero) elements of the diagonal. If this is not sufficient to ensure that the Hungarian algorithm finds a different solution, then the number along the diagonal is increased until it does. In the absence of permutation descent, kickstart was performed differently. KickstartV randomly selects a fraction, 5%, of the vertices and randomly recolours them.