ICAIIC 2025 · Conference Paper · IEEE
GCP RL: RLTB
Graph Coloring Problem solved via Reinforcement Learning & Graph Neural Networks. Conducted as my graduation research and published as first author at the International Conference on Artificial Intelligence in Information and Communication, 2025.
Overview
Abstract & Architecture
We present a hybrid approach combining Reinforcement Learning (RL) with TabuCol — a tabu search variant specifically designed for the Graph Coloring Problem (GCP) — enhanced by Graph Neural Networks (GNNs).
Our model, RLTB, integrates a Deep Q-Network (DQN) architecture with multiple GNN layers to select promising (node, color) pairs, guiding the RL agent toward optimal solutions by leveraging rich, topology-aware node embeddings as state representations.
Experimental evaluations on standard DIMACS benchmark instances demonstrate that RLTB significantly outperforms existing heuristic algorithms such as TabuCol and greedy baselines, surpasses GNN-based methods from prior work, and shows competitive performance against other outstanding hybrid approaches.
Graph Topology