Monte Carlo Graph Coloring
This addresses the scalability issue in graph coloring for researchers and practitioners, but it is incremental as it adapts known Monte Carlo methods to a new domain.
The paper tackles the graph coloring problem by applying Monte Carlo search algorithms, specifically NMCS and NRPA, and compares this approach to existing heuristics, showing it can handle instances beyond the few hundred vertices limit of exact methods.
Graph Coloring is probably one of the most studied and famous problem in graph algorithms. Exact methods fail to solve instances with more than few hundred vertices, therefore, a large number of heuristics have been proposed. Nested Monte Carlo Search (NMCS) and Nested Rollout Policy Adaptation (NRPA) are Monte Carlo search algorithms for single player games. Surprisingly, few work has been dedicated to evaluating Monte Carlo search algorithms to combinatorial graph problems. In this paper we expose how to efficiently apply Monte Carlo search to Graph Coloring and compare this approach to existing ones.