Heuristic graph colouring using hypergraph representations.

Abstract

We revisit the classic Graph Colouring problem in the context of column partitioning of matrices. In this context, we are given a hypergraph and the aim is to colour the vertices of the hypergraph by a minimum number of colours such that in each hyperedge every colour occurs at most once. We provide a comprehensive implementation and experimental evaluation of combinations of known heuristical techniques such as vertex orderings for greedy colouring, vertex reordering after an initial colouring, and recolouring of vertices to save colours. In addition, we provide a new stronger recolouring method that is based on the hypergraph view of the problem. Our implementation is specifically tailored towards efficiency on hypergraph instances. We compare our implementation with the ColPack library and find that several heuristics not contained in ColPack yield solutions with fewer colours at the cost of higher but still affordable running times. We complement these results by a theoretical analysis of the problem complexity on hypergraphs that can be covered by few hyperedges.