The maximum independent set (MIS) problem, a classical NP-hard problem with
extensive applications in various areas, aims to find the 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 framework for MIS called ARIR, which
encompasses two main parts: a lightweight adaptive mechanism and a novel
inexact efficient reduction rule to simplify instances. Based on ARIR, three
algorithms -- ARIR-I, ARIR-II, and ARIR-III -- are developed by adopting three
distinct reduction strategies. We conduct experiments on five benchmarks,
encompassing 92 instances. Compared with six state-of-the-art algorithms, our
ARIR-based algorithms offer the best accuracy on the majority of instances,
while obtaining competitive results on the remaining instances.

本文研究了应用广泛的 NP-hard 问题之一，最大独立集问题（ M IS），提出了局部搜索框架 ARIR 及其三种算法，采用三种不同的减少策略，在五组基准测试中显示出明显的优越性。

最大独立集问题的自适应重复交集约简局部搜索

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

We show that the maximum independent set problem (MIS) on an $n$-vertex graph
can be solved in $1.1996^nn^{O(1)}$ time and polynomial space, which even is
faster than Robson's $1.2109^{n}n^{O(1)}$-time exponential-space algorithm
published in 1986. We also obtain improved algorithms for MIS in graphs with
maximum degree 6 and 7, which run in time of $1.1893^nn^{O(1)}$ and
$1.1970^nn^{O(1)}$, respectively. Our algorithms are obtained by using fast
algorithms for MIS in low-degree graphs in a hierarchical way and making a
careful analyses on the structure of bounded-degree graphs.

本研究提出了一种基于低度图的层次快速算法，可以在多项式空间复杂度内解决最大独立集问题，并得到了在不同最大度的图形中最大独立集问题的改进算法。