# Solving NP-Hard Problems on Graphs with Extended AlphaGo Zero

arXiv: https://arxiv.org/abs/1905.11623 · HTML: https://mlsanity.com/paper/1905.11623/

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 May 2019.

## Built on by (most cited first, 23 of 23)

- [Sym-NCO: Leveraging Symmetricity for Neural Combinatorial Optimization](https://mlsanity.com/paper/2205.13209/) (2022)
- [Simulation-guided Beam Search for Neural Combinatorial Optimization](https://mlsanity.com/paper/2207.06190/) (2022)
- [RL4CO: an Extensive Reinforcement Learning for Combinatorial Optimization Benchmark](https://mlsanity.com/paper/2306.17100/) (2023)
- [A Survey on Influence Maximization: From an ML-Based Combinatorial Optimization](https://mlsanity.com/paper/2211.03074/) (2022)
- [Finding Backdoors to Integer Programs: A Monte Carlo Tree Search Framework](https://mlsanity.com/paper/2110.08423/) (2021)
- [Deep Reinforcement Learning for Exact Combinatorial Optimization: Learning to Branch](https://mlsanity.com/paper/2206.06965/) (2022)
- [Qubit Routing using Graph Neural Network aided Monte Carlo Tree Search](https://mlsanity.com/paper/2104.01992/) (2021)
- [Deep learning-driven scheduling algorithm for a single machine problem minimizing the total tardiness](https://mlsanity.com/paper/2402.14847/) (2024)
- [A Unified Framework for Combinatorial Optimization Based on Graph Neural Networks](https://mlsanity.com/paper/2406.13125/) (2024)
- [Investment vs. reward in a competitive knapsack problem](https://mlsanity.com/paper/2101.10964/) (2021)
- [Abelian Neural Networks](https://mlsanity.com/paper/2102.12232/) (2021)
- [BalMCTS: Balancing Objective Function and Search Nodes in MCTS for Constraint Optimization Problems](https://mlsanity.com/paper/2312.15864/) (2023)
- [AlphaMapleSAT: An MCTS-based Cube-and-Conquer SAT Solver for Hard Combinatorial Problems](https://mlsanity.com/paper/2401.13770/) (2024)
- [Zero Training Overhead Portfolios for Learning to Solve Combinatorial Problems](https://mlsanity.com/paper/2102.03002/) (2021)
- [Attention-based UAV Trajectory Optimization for Wireless Power Transfer-assisted IoT Systems](https://mlsanity.com/paper/2502.17517/) (2025)
- [Solving Graph-based Public Good Games with Tree Search and Imitation Learning](https://mlsanity.com/paper/2106.06762/) (2021)
- [AlphaSnake: Policy Iteration on a Nondeterministic NP-hard Markov Decision Process](https://mlsanity.com/paper/2211.09622/) (2022)
- [RELS-DQN: A Robust and Efficient Local Search Framework for Combinatorial Optimization](https://mlsanity.com/paper/2304.06048/) (2023)
- [Solving the Kidney-Exchange Problem via Graph Neural Networks with No Supervision](https://mlsanity.com/paper/2304.09975/) (2023)
- [One Model, Any Conjunctive Query: Graph Neural Networks for Answering Queries over Incomplete Knowledge Graphs](https://mlsanity.com/paper/2409.13959/) (2024)
- [Preference-Based Gradient Estimation for ML-Guided Approximate Combinatorial Optimization](https://mlsanity.com/paper/2502.19377/) (2025)
- [DOPPLER: Dual-Policy Learning for Device Assignment in Asynchronous Dataflow Graphs](https://mlsanity.com/paper/2505.23131/) (2025)
- [Exploiting Low-Rank Objective Structure in Discrete Quadratic Optimization](https://mlsanity.com/paper/2602.20376/) (2026)

## Abstract (arXiv)

There have been increasing challenges to solve combinatorial optimization problems by machine learning. Khalil et al. proposed an end-to-end reinforcement learning framework, S2V-DQN, which automatically learns graph embeddings to construct solutions to a wide range of problems. To improve the generalization ability of their Q-learning method, we propose a novel learning strategy based on AlphaGo Zero which is a Go engine that achieved a superhuman level without the domain knowledge of the game. Our framework is redesigned for combinatorial problems, where the final reward might take any real number instead of a binary response, win/lose. In experiments conducted for five kinds of NP-hard problems including sc MinimumVertexCover and sc MaxCut, our method is shown to generalize better to various graphs than S2V-DQN. Furthermore, our method can be combined with recently-developed graph neural network (GNN) models such as the Graph Isomorphism Network, resulting in even better performance. This experiment also gives an interesting insight into a suitable choice of GNN models for each task.