  Kernelization is a general theoretical framework for preprocessing instances
of NP-hard problems into (generally smaller) instances with bounded size, via
the repeated application of data reduction rules. For the fundamental Max Cut
problem, kernelization algorithms are theoretically highly efficient for
various parameterizations. However, the efficacy of these reduction rules in
practice---to aid solving highly challenging benchmark instances to
optimality---remains entirely unexplored.
  We engineer a new suite of efficient data reduction rules that subsume most
of the previously published rules, and demonstrate their significant impact on
benchmark data sets, including synthetic instances, and data sets from the VLSI
and image segmentation application domains. Our experiments reveal that current
state-of-the-art solvers can be sped up by up to multiple orders of magnitude
when combined with our data reduction rules. On social and biological networks
in particular, kernelization enables us to solve four instances that were
previously unsolved in a ten-hour time limit with state-of-the-art solvers;
three of these instances are now solved in less than two seconds.
