Distributed Reductions for the Maximum Weight Independent Set Problem

Finding maximum-weight independent sets in graphs is an important NP-hard optimization problem. Given a vertex-weighted graph \(G\), the task is to find a subset of pairwise non-adjacent vertices of \(G\) with maximum weight. Most recently published practical exact algorithms and heuristics for this problem use a variety of data-reduction rules to compute (near- )optimal solutions. Applying these rules results in an equivalent instance of reduced size. An optimal solution to the reduced instance can be easily used to construct an optimal solution for the original input.