4:20 PM - 4:40 PM
[1Q3-J-2-04] Learning to Find Hard Instances of Graph Problems
Keywords:hard instance, graph, algorithm, reinforcement learning
In this paper, We aim at automatically generating hard instances of graph problems. We formulate finding hard instances of graph problems as an optimization problem and propose a method to automatically find hard instances by solving the optimization problem. The advantage of the proposed algorithm is that it does not require any task-specific knowledge. To the best of our knowledge, it is the first non-trivial method in the literature to automatically find hard instances by using optimization.
Through experiments on various problems, we show that our proposed method can generate a few to several orders of magnitude harder instances than the random based approach in many settings, and especially our method outperforms rule-based algorithms in the 3-coloring problem.