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.
翻译:数据减少规则是算法工具箱中处理具有计算挑战性问题的既定方法。 数据减少规则是一种多式时间算法, 以输入、 输出等效、 通常较少的同一问题为例。 在问题处理前, 应用数据减少规则在许多情况下可以大大缩小其规模, 甚至直接解决这些问题。 通常, 这些数据减少规则是详尽无遗地应用的, 在某些固定的顺序下, 以获得不可复制的事例。 人们经常看到, 通过改变规则的顺序, 可以得到不同的不可复制的例子。 我们提议在不可复制的事例中“ 不适用” 数据减少规则, 从而扩大这些结果, 然后再应用数据减少规则来缩小它们。 我们表明, 这种有点反直观性的做法可以导致大大缩小其规模, 甚至直接地减少规则。 取消数据减少规则的过程不限于“ 倒退” 适用于预处理期间的情况。 相反, 我们制定所谓的后向规则, 基本上可以消除数据减少规则, 但是不使用任何关于数据减少规则的“ 无法复制” 信息, 然后再次应用数据减少规则来缩小它们。 我们用这个“ 递增缩” 模式, 。 。