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.

翻译：最大独立的一组问题(MIS)是一个典型的NP-硬性问题,在各个领域广泛应用,目的是找到一套最大的脊椎,其中没有边际。由于可计算性,很难有效地解决管理信息系统问题,特别是在大图表上。在可接受的时间范围内采用超自然方法以获得一个好的解决办法,在文献中引起了很大的注意。在本文中,我们建议对称为ARIR的MIS采用一个高效的本地搜索算法,它由两个主要部分组成:适应性的当地搜索框架和简化案例的新颖的不精确有效削减规则。我们用五个基准进行实验,包括92个实例。与四种最先进的算法相比,ARIR提供了89个案例的最佳准确性,并在其余三个案例中取得了竞争性结果。