Boosting Data Reduction for the Maximum Weight Independent Set Problem Using Increasing Transformations

Alexander Gellner, Sebastian Lamm, Christian Schulz +2

Given a vertex-weighted graph, the maximum weight independent set problem asks for a pair-wise non-adjacent set of vertices such that the sum of their weights is maximum. The branc…