  Data reduction rules are an established method in the algorithmic toolbox for
tackling computationally challenging problems. A data reduction rule is a
polynomial-time algorithm that, given a problem instance as input, outputs an
equivalent, typically smaller instance of the same problem. The application of
data reduction rules during the preprocessing of problem instances allows in
many cases to considerably shrink their size, or even solve them directly.
Commonly, these data reduction rules are applied exhaustively and in some fixed
order to obtain irreducible instances. It was often observed that by changing
the order of the rules, different irreducible instances can be obtained. We
propose to "undo" data reduction rules on irreducible instances, by which they
become larger, and then subsequently apply data reduction rules again to shrink
them. We show that this somewhat counter-intuitive approach can lead to
significantly smaller irreducible instances. The process of undoing data
reduction rules is not limited to "rolling back" data reduction rules applied
to the instance during preprocessing. Instead, we formulate so-called backward
rules, which essentially undo a data reduction rule, but without using any
information about which data reduction rules were applied to it previously. In
particular, based on the example of Vertex Cover we propose two methods
applying backward rules to shrink the instances further. In our experiments we
show that this way smaller irreducible instances consisting of real-world
graphs from the SNAP and DIMACS datasets can be computed.
