Lu, H., Halappanavar, M., Chavarria-Miranda, D., Gebremedhin, A. H., Panyala, A., & Kalyanaraman, A. (2016). Algorithms for balanced graph colorings with applications in parallel computing. IEEE Transactions on Parallel and Distributed Systems, 28(5), 1240-1256.
In this paper, Lu et al. present parallel approaches for balanced graph coloring. Graph coloring is an important problem in parallel computing, where the goal is to assign colors to the vertices of a graph such that no two adjacent vertices share the same color. It is an NP-hard problem because, given a coloring, it is easy to verify if it is valid, but one cannot confirm whether a coloring is optimal in polynomial time. Graph coloring has applications in scheduling, register allocation, scheduling and timetabling problems - or scheduling garbage collecting trucks in New York City.
Graph coloring is used to identify subsets of independent tasks in parallel computing, where each task can be executed without interference from others. However, if the color classes produced have a skew, utilization of resources becomes inefficient. Equitable coloring aims to balance the sizes of color classes, such that the bin size of each color class does not differ by more than one. Lu et al. refer to a practical relaxation of equitable coloring as balanced coloring. They study two variants of the problem: distance-1 coloring (the standard coloring problem) and partial distance-2 coloring (coloring one vertex set in a bipartite graph).
Lu et al. note that standard coloring approaches aim at minimizing the number of colors used, without any considerations of the size of the color classes. By their nature, these approaches produce highly skewed color classes. To address this, they propose two classes of algorithms: the first category aims to obtain a balanced coloring in a single attempt (ab initio), while the second category begins with a standard coloring and then modifies it to achieve balance (guided).
Greedy algorithms for graph coloring are often used in practice. These differ based on (a) the order in which vertices are processed, and by (b) the strategy used to select colors. A common strategy with regards to (a) is to rank vertices in a descending order of their degrees (or the number of colored neighbors, or differently colored neighbors). A common strategy for (b) is to select the smallest permissible color for a vertex in each step - First Fit (FF).
Lu et al. discuss two approaches for ab initio balanced coloring: (a) Greedy-LU, where a vertex is assigned the least used permissible color; and (b) Greedy-Random, where a random permissible color is assigned to a vertex. Among guided approaches, they discuss: (a) Shuffling-based method, where a subset of vertices are moved from over-full bin to under-full bins; and (b) Recoloring-based method, where all vertices are recolored based on ordering of vertices based on the coloring obtained from a standard Greedy-FF algorithm. After applying Greedy-FF, vertices can be ordered such that vertices of the same color are grouped together. This recoloring is guaranteed to require the same of fewer colors. Even better, list the color classes in reverse order (i.e. the smallest size color class is processed first). To ensure balance, while recoloring, choose the smallest color which is under full.
Refer to the PDF for more details on the algorithms and their performance.
