Efficient Algorithms for Graph Coloring on GPU

Graph coloring is an important problem in computer science and engineering with numerous applications. As the size of data increases today, graphs with millions of nodes are becoming commonplace. Parallel graph coloring algorithms on high throughput graphics processing units (GPUs) have recently been proposed to color such large graphs efficiently. We present two new graph coloring algorithms for GPUs which improve upon existing algorithms both in coloring speed and quality. The first algorithm, counting-based Jones-Plassmann (CJP), uses counters to implement the classic Jones-Plassmann parallel coloring heuristic in a work-efficient manner. The second algorithm, conflict coloring (CC) achieves higher parallelism than CJP, and is based on optimistically coloring the graph using estimates of the chromatic number. We compared CC and CJP with two state-of-the-art GPU coloring algorithms, csrcolor [1] and Deveci et al's [2] vertex/edge-based algorithms (which we call VEB), as well as the sequential CPU algorithm ColPack [3]. In terms of coloring quality, CJP and CC are both far better than csrcolor, while CJP uses 10% fewer colors than VEB on average and CC uses 10% more. Compared to ColPack, CJP and CC use 1.3 x and 1.5x more colors on nonbipartite graphs, resp. In terms of speed, CJP is on average 1.5 - 2x faster than the other algorithms, while CC is 2.7 - 4.3x faster.