Kavli Affiliate: Yi Zhou
| First 5 Authors: Yiping Liu, Yi Zhou, Zhenxiang Xu, Mingyu Xiao, Jin-Kao Hao
| Summary:
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 harvest planning, 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 pre-processing, the
initial solution generation, and the local search components in a
computationally efficient way. The RLS is empirically evaluated on 278 graphs
arising from different application scenarios. The results indicates that the
RLS is highly competitive — For most graphs, it achieves significantly
superior solutions compared to 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 the data reduction plays a key
role in achieving such a competitive performance.
| Search Query: ArXiv Query: search_query=au:”Yi Zhou”&id_list=&start=0&max_results=3