A Near-Real-Time Reduction-Based Algorithm for Coloring Massive Graphs

The graph coloring problem is a classical combinatorial optimization problem with important applications such as register allocation and task scheduling, and it has been extensively studied for decades. However, near-real-time algorithms that can deliver high-quality solutions for very large real-world graphs within a strict time frame remain relatively underexplored. In this paper, we try to bridge this gap by systematically investigating reduction rules that shrink the problem size while preserving optimality. For the first time, domination reduction, complement crown reduction, and independent set reduction are applied to large-scale instances. Building on these techniques, we propose RECOL, a reduction-based algorithm that alternates between fast estimation of lower and upper bounds, graph reductions, and heuristic coloring. We evaluate RECOL on a wide range of benchmark datasets, including SNAP, the Network Repository, DIMACS10, and DIMACS2. Experimental results show that RECOL consistently outperforms state-of-the-art algorithms on very large sparse graphs within one minute. Additional experiments further highlight the pivotal role of reduction techniques in achieving this performance.