15.2. Reduction Rules

Recall the definition of a data reduction rule. In some instances, a single reduction rule is good enough to guarantee that a fully reduced instance with respect to this rule is a problem kernel. For most problems, however, we need more than one reduction rule if we want to prove that once none of these rules is applicable anymore, the current fully reduced instance is a problem kernel. We illustrate this using the vertex cover and cluster editing problems as examples.