Graph Coloring problem solving using monte carlo tree search and deep reinforcement learning

Wenzhu Yang () and Zhanshan Li ()
Additional contact information
Wenzhu Yang: Jilin University
Zhanshan Li: Jilin University

Journal of Combinatorial Optimization, 2025, vol. 50, issue 2, No 8, 21 pages

Abstract: Abstract The graph coloring problem, as a well-known NP-hard problem, holds significant value in practical applications. In this paper, a self-learning method that combines Monte Carlo tree search with deep reinforcement learning is proposed to efficiently solve the graph coloring problem. This method offers two principal advantages. Firstly, it leverages deep reinforcement learning to eliminate the necessity for manual feature construction and data labeling. Secondly, by combining the neural network with Monte Carlo tree search, the neural network can provide comprehensive guidance based on the structural information of the graph, facilitating a more effective balance between exploration and exploitation, thereby leading to superior solutions. Finally, experimental results demonstrate that the method proposed herein has distinct advantages over existing graph coloring algorithms. Moreover, this approach also exhibits outstanding performance when dealing with graph instances whose vertex size surpasses those encountered during the training phase.

Keywords: Combinatorial optimization; Graph coloring; Deep reinforcement learning; Monte Carlo tree search; Graph neural network; ACM Computing Classification: 10010147; 10010178; 10010205; 10010209; 10010147; 10010257; 10010293; 10010294 (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-025-01338-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:50:y:2025:i:2:d:10.1007_s10878-025-01338-8

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-025-01338-8

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().