Combining Reinforcement Learning and Heuristic Optimization: A Model Based on a Deep Q-Network and Graph Neural Networks for Graph Coloring

We present a hybrid approach combining Reinforcement Learning (RL) with the TabuCol, which is a version of tabu search specifically designed for the Graph Coloring Problem (GCP), enhanced by Graph Neural Networks (GNNs), to tackle the GCP. Our model, referred to as RLTB, integrates a Deep Q-Network architecture with multiple GNN layers to select promising (node, color) pairs, guiding the RL agent towards optimal solutions. Experimental evaluations on standard DIMACS graph instances demonstrate that RLTB significantly outperforms existing heuristic algorithms such as Tabucol and a greedy algorithm, surpasses GNN methods from other papers, and shows competitive performance against other outstanding hybrid methods.

I. Introduction

Many optimization problems can be represented as graph problems, among which the Graph Coloring Problem (GCP) is one of the most well-known. GCP involves coloring the vertices of a graph such that no adjacent nodes share the same color while minimizing the total number of colors used. GCP has been extensively researched and applied in various real-world fields, such as register allocation [1], frequency assignment [2], and scheduling [3]. GCP is particularly sig-nificant because it is an NP-hard problem, meaning it plays a central role in computational complexity theory, especially in the context of the P versus NP question. Since GCP is NP-hard, no algorithm is known to solve it in polynomial time, making it a key target for heuristic and approximation methods.