Vonarburg-Shmaria

M. Besta, A. Carigiet, Z. Vonarburg-Shmaria, K. Janda, L. Gianinazzi, T. Hoefler. High-Performance Parallel Graph Coloring with Strong Guarantees on Work, Depth, and Quality. In Proceedings of the IEEE/ACM International Conference on High Performance Computing, Networking, Storage and Analysis (SC20), (acceptance rate: 25%).

Parallel Graph Coloring

This paper was accepted to ACM/IEEE Supercomputing 20. You can find out more about SC20 Conference or visit their Wikipedia page. Find the full version of the paper on arXiv. I co-authored this paper with Maciej Besta (main author), inter alia, from the Scalable Parallel Computing Laboratory (ETH Zurich) SPCL.

Fast vertex degeneracy ordering

We develop the first parallel graph coloring heuristics with strong theoretical guarantees on work and depth and coloring quality. The key idea is to design a relaxation of the vertex degeneracy order, a well-known graph theory concept, and to color vertices in the order dictated by this relaxation. This introduces a tunable amount of parallelism into the degeneracy ordering that is otherwise hard to parallelize. This simple idea enables significant benefits in several key aspects of graph coloring. For example, one of our algorithms ensures polylogarithmic depth and a bound on the number of used colors that is superior to all other parallelizable schemes, while maintaining work-efficiency. In addition to provable guarantees, the developed algorithms have competitive run-times for several real-world graphs, while almost always providing superior coloring quality. Our degeneracy ordering relaxation is of separate interest for algorithms outside the context of coloring.