A wide-ranging computational comparison of high-performance graph colouring algorithms

Abstract

This paper reviews the current state of the literature surrounding methods for the general graph colouring problem and presents a broad comparison of six high-performance algorithms, each belonging to one of the main algorithmic schemes identified. Unlike many previous computational studies in graph colouring, a large range of both artificially generated and real-world graphs are considered, culminating in over 40,000 individual trials that have consumed more than a decade of computation time in total. The picture painted by the comparison is complex, with each method outperforming all others on at least one occasion; however, general patterns are also observed, particularly with regards to the advantages of hybridising local-search techniques with global-based operators.

Introduction

The graph colouring problem is a classical NP-hard combinatorial optimisation problem with practical applications in various branches of operational research including school and university timetabling [14], [16], [56], sports scheduling [59], frequency assignment [6], [78], compiler register allocation [18], and short-circuit testing [40]. Graph colouring involves assigning a “colour” to each vertex in a graph such that adjacent vertices are allocated different colours, with the number of colours being minimised [46], [65]. Formally, given an undirected simple graph $G=(V,E)$, with vertex set V and edge set E, the task is to assign each vertex $v\in V$ an integer $c(v)\in \{\mathrm{1,2},\dots ,k\}$ such that:

• $c(v)\ne c(u)$ $\forall \{v,u\}\in E$ and

• k is minimised.

In addition to its underlying computational complexity, the graph colouring problem presents considerable challenges due to the sheer variety of graph structures that can be encountered in practice. Some graphs, for example, are generated so that the degrees of the vertices are modelled by a particular probability function, or such that the vertices and edges correspond to specific geometric objects and configurations. Graphs can also be produced so that their solutions fulfil certain properties such as the number of colours that are needed, and/or the number of vertices assigned to each colour class. Graphs arising from practical problems can also exhibit certain features: e.g. graphs that model timetabling problems may contain various large cliques,¹ or exhibit some clustering of the vertices [72]. If the existence of such structures is known beforehand then algorithms might be tailored to exploit this information, perhaps leading to improvements in performance. However, the identification of such structures is not always easy and, indeed, is often a computationally intractable task in itself [49].

The past four decades have seen very many articles proposing algorithms for the graph colouring problem, ranging from simple constructive techniques [79] to sophisticated hybrid metaheuristics [37], [45], [61], [74]. Comparisons of such algorithms have generally been conducted empirically, and a useful development occurred in 1992 with the organisation of the Second DIMACS Implementation Challenge [2], which resulted in a suite of differently structured graph colouring problems being placed into the public domain. In addition, various problem generators have also been made available online for practitioners who are interested in testing their algorithms on particular types of problem instance [4]. However, despite these developments we suggest that it is often difficult to assess from the literature the relative benefits of different graph colouring algorithms, particularly due to the following reasons.

• Although many studies make use of publicly available problem instances or generators, experimental conditions usually alter from paper to paper. In particular, researchers often perform different numbers of trials-per-instance, use different performance metrics, and/or impose different computation limits. In cases where sets of benchmark instances are used, researchers also often direct their efforts towards gaining good results on just a subset of problems.

• Related to this, many research papers only report results achieved at the imposed cut-off point, giving little indication of how an algorithm progresses from the initial solution towards the final reported solution.

• In some cases researchers also enhance results using existing knowledge on the structure of a problem instance to tune their algorithms. For example, the minimal number of colours needed to colour the graph might be known in advance, or details may be available as to how the problem was generated. Of course, on the one hand tuning an algorithm may help to give readers a true appreciation of its capabilities; however, such actions also go against the general aim of an approximation algorithm, which is to produce good quality results while assuming no such specialist knowledge on behalf of the user.

Given these issues, in this work our aim is to provide an instructive comparative analysis on a range of different graph colouring algorithms, some of which are currently claimed to be “state of the art”. To achieve this, we consider the performance of six methods, using at least one from each of the main algorithmic schemes identified in the next section. We also avoid some of the pitfalls above by (a) analysing algorithm performance using a platform-independent performance metric; (b) using a very large sample of problem instances (over 5000); and (c) by executing algorithms blindly, meaning that no problem knowledge is assumed on behalf of the user before a run is started.

In the next section we start by reviewing some of the more prominent algorithms proposed for the graph colouring problem over the past 40 years, identifying common schemes. Other reviews can be found in [38], [45], [54]. Section 3 then contains a more detailed description of the six algorithms considered in our comparison, with Section 4 detailing the results. Section 5 concludes the paper.