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…