  Reductions---rules that reduce input size while maintaining the ability to
compute an optimal solution---are critical for developing efficient maximum
independent set algorithms in both theory and practice. While several simple
reductions have previously been shown to make small domain-specific instances
tractable in practice, it was only recently shown that advanced reductions (in
a measure-and-conquer approach) can be used to solve real-world networks on
millions of vertices [Akiba and Iwata, TCS 2016]. In this paper we compare
these state-of-the-art reductions against a small suite of simple reductions,
and come to two conclusions: just two simple reductions---vertex folding and
isolated vertex removal---are sufficient for many real-world instances, and
further, the power of the advanced rules comes largely from their initial
application (i.e., kernelization), and not their repeated application during
branch-and-bound. As a part of our comparison, we give the first experimental
evaluation of a reduction based on maximum critical independent sets, and show
it is highly effective in practice for medium-sized networks.
