A Reduction-Driven Local Search for the Generalized Independent Set Problem

The Generalized Independent Set (GIS) problem extends the classical maximum independent set problem by incorporating profits for vertices and penalties for edges. This generalized problem has been identified in diverse applications in fields such as forest harvesting, competitive facility location, social network analysis, and even machine learning. However, solving the GIS problem in large-scale, real-world networks remains computationally challenging. In this paper, we explore data reduction techniques to address this challenge. We first propose 14 reduction rules that can reduce the input graph with rigorous optimality guarantees. We then present a reduction-driven local search (RLS) algorithm that integrates these reduction rules into the preprocessing, the initial solution generation, and the local search components in a computationally efficient way. The RLS is empirically evaluated on 278 graphs drawn from different application scenarios. The results indicate that the RLS is highly competitive: for most graphs, it achieves significantly superior solutions compared with other known solvers, and it effectively provides solutions for graphs exceeding 260 million edges, a task at which every other known method fails. Analysis also reveals that data reduction plays a key role in achieving such a competitive performance.

History: Accepted by Erwin Pesch, Area Editor for Heuristic Search and Approximation Algorithms.

Funding: This research was supported by the National Natural Science Foundation of China [Grants 62372093 and 62372095].

Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2025.1203 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2025.1203 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .