On the Power of Simple Reductions for the Maximum Independent Set Problem

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.