2 papers
cs.DS2026
A Comprehensive Survey of Data Reduction Rules for the Maximum Weighted Independent Set Problem
Ernestine GroÃmann, Kenneth Langedal, Christian Schulz
The Maximum Weight Independent Set (MWIS) problem, as well as its related problems such as Minimum Weight Vertex Cover, are fundamental NP-hard problems with numerous practical app…
math.OC2025
Accelerating Reductions Using Graph Neural Networks and a New Concurrent Local Search for the Maximum Weight Independent Set Problem
Ernestine GroÃmann, Kenneth Langedal, Christian Schulz
The Maximum Weight Independent Set problem is a fundamental NP-hard problem in combinatorial optimization with several real-world applications. Given an undirected vertex-weighted…