A Reduction-Driven Local Search for the Generalized Independent Set Problem
Yiping Liu, Yi Zhou, Zhenxiang Xu, Mingyu Xiao, Jin-Kao Hao · 2025
Read A Reduction-Driven Local Search for the Generalized Independent Set Problem by Yiping Liu, Yi Zhou, Zhenxiang Xu, Mingyu Xiao, Jin-Kao Hao (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-21052.txt.
Description
Liu, Zhou, Xu, Xiao, and Hao design in twenty twenty-five a search method for picking profitable node sets in huge networks under edge penalties. The problem generalises the classic independent set problem and appears in forestry, facility siting, and social network work. Large real networks make it hard to solve well.
They first craft fourteen reduction rules that shrink a graph while guaranteeing the best answer survives. Their search then weaves those rules through setup, starting solutions, and local improvement. On several hundred graphs from varied fields, the method beat known solvers on most cases. It even solved graphs with hundreds of millions of edges, where every rival failed. Analysis credits the reductions for much of the edge.
Catalog record
| CREATOR | Yiping Liu, Yi Zhou, Zhenxiang Xu, Mingyu Xiao, Jin-Kao Hao |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 112 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-21052