  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 branch-and-reduce paradigm is the de facto standard
approach to solve the problem to optimality in practice. In this paradigm, data
reduction rules are applied to decrease the problem size. These data reduction
rules ensure that given an optimum solution on the new (smaller) input, one can
quickly construct an optimum solution on the original input.
  We introduce new generalized data reduction and transformation rules for the
problem. A key feature of our work is that some transformation rules can
increase the size of the input. Surprisingly, these so-called increasing
transformations can simplify the problem and also open up the reduction space
to yield even smaller irreducible graphs later throughout the algorithm. In
experiments, our algorithm computes significantly smaller irreducible graphs on
all except one instance, solves more instances to optimality than previously
possible, is up to two orders of magnitude faster than the best
state-of-the-art solver, and finds higher-quality solutions than heuristic
solvers DynWVC and HILS on many instances. While the increasing transformations
are only efficient enough for preprocessing at this time, we see this as a
critical initial step towards a new branch-and-transform paradigm.
