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

CREATORYiping Liu, Yi Zhou, Zhenxiang Xu, Mingyu Xiao, Jin-Kao Hao
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE112 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-21052

Browse the full library · About the Tower of Babel