QUBO Formulations for Arithmetic Progression Graph Labeling Problems

Abstract

The Arithmetic Progression Graph Labeling is an NP-complete problem with various applications, including optimizing scheduling problems. This paper presents Quadratic Unconstrained Boolean Optimization (QUBO) solutions for the version with fixed vertex labels of this problem, then the original general problem. We use and compare standard (D-Wave Advantage and Advantage 2 Prototype) and hybrid (D-Wave Leap Hybrid Solver Service) methods to solve these problems with D-Wave quantum machines. Our experiments suggest that the hybrid methods outperform the standard ones.