Finding Increasingly Large Extremal Graphs with AlphaZero and Tabu Search
This addresses a central problem in extremal graph theory for researchers, but it is incremental as it builds on existing methods to achieve better bounds.
The paper tackled the problem of finding extremal graphs that maximize edges without 3- or 4-cycles, improving state-of-the-art lower bounds for several graph sizes using AlphaZero and tabu search with a curriculum approach.
This work studies a central extremal graph theory problem inspired by a 1975 conjecture of Erdős, which aims to find graphs with a given size (number of nodes) that maximize the number of edges without having 3- or 4-cycles. We formulate this problem as a sequential decision-making problem and compare AlphaZero, a neural network-guided tree search, with tabu search, a heuristic local search method. Using either method, by introducing a curriculum -- jump-starting the search for larger graphs using good graphs found at smaller sizes -- we improve the state-of-the-art lower bounds for several sizes. We also propose a flexible graph-generation environment and a permutation-invariant network architecture for learning to search in the space of graphs.