Using an Incomplete Version of Dynamic Backtracking for Graph Colouring

This paper investigates a simple, constructive search strategy: an incomplete version of Ginsberg's Dynamic Backtracking which records no information during search, and randomly selects variables for backtracking. Combining this with forward checking and dynamic variable ordering heuristics we obtain algorithms for constraint satisfaction problems, and by adding branch-and-bound we obtain optimization algorithms. Testing these on several classes of 1000-vertex graph colouring problems we find colourings which are competitive with those of specialized algorithms: a 92-colouring for a random graph (p = 0.5), hidden k-colourings in equipartite graphs (p = 0.5) for k ≤ 60 and improved results for geometric graphs. An interesting aspect is that most of our results were obtained using the precise opposite of the well-known first-fail principle.