Quantum computing and the stable set problem

Aljaž Krpan, Janez Povh, Dunja Pucher

Published 2024-05-21Version 1

Given an undirected graph, the stable set problem asks to determine the cardinality of the largest subset of pairwise non-adjacent vertices. This value is called the stability number of the graph, and its computation is an NP-hard problem. In this paper, we focus on solving the stable set problem using the D-wave quantum annealer. By formulating the problem as a quadratic unconstrained binary optimization problem with the penalty method, we show that the optimal value of this formulation is equal to the stability number of the graph for certain penalty parameter values. However, D-Wave's quantum annealer is not an exact solver, so the solutions may be far from the optimum and may not even represent stable sets. To address this, we introduce a post-processing procedure that identifies samples that could lead to improved solutions and extracts stable sets from them. Additionally, we propose a so-called simple CH-partitioning method to handle larger instances that cannot be embedded on D-Wave's quantum processing unit. Finally, we investigate how different penalty parameter values affect the solutions' quality. Extensive computational results show that the post-processing procedure significantly improves the solution quality, while the simple CH-partitioning method successfully extends our approach to medium-size instances.