Learning-augmented Maximum Independent Set

Authors: Vladimir Braverman, Prathamesh Dharangutte, Vihan Shah, Chen Wang.

Conference: International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX'24)

Abstract: We study the Maximum Independent Set (MIS) problem on general graphs within the framework of learning-augmented algorithms. The MIS problem is known to be NP-hard and is also NP-hard to approximate to within a factor of n^{1-\delta} for any \delta>0. We show that we can break this barrier in the presence of an oracle obtained through predictions from a machine learning model that answers vertex membership queries for a fixed MIS with probability 1/2+\eps. In the first setting we consider, the oracle can be queried once per vertex to know if a vertex belongs to a fixed MIS, and the oracle returns the correct answer with probability 1/2 + \eps. Under this setting, we show an algorithm that obtains an O~(\sqrt{\Delta}/\eps)-approximation in O(m) time where \Delta is the maximum degree of the graph. In the second setting, we allow multiple queries to the oracle for a vertex, each of which is correct with probability 1/2 + \varepsilon. For this setting, we show an O(1)-approximation algorithm using O(n/\eps^2) total queries and O~(m) runtime.