An Adaptive Repeated-Intersection-Reduction Local Search for the Maximum Independent Set Problem

The maximum independent set (MIS) problem, a classical NP-hard problem with extensive applications in various areas, aims to find a largest set of vertices with no edge among them. Due to its computational intractability, it is difficult to solve the MIS problem effectively, especially on large graphs. Employing heuristic approaches to obtain a good solution within an acceptable amount of time has attracted much attention in literature. In this paper, we propose an efficient local search algorithm for MIS called ARIR, which consists of two main parts: an adaptive local search framework, and a novel inexact efficient reduction rule to simplify instances. We conduct experiments on five benchmarks, encompassing 92 instances. Compared with four state-of-the-art algorithms, ARIR offers the best accuracy on 89 instances and obtains competitive results on the three remaining instances.