Data reductions and combinatorial bounds for improved approximation algorithms.

Kernelization algorithms in the context of Parameterized Complexity are often based on a combination of data reduction rules and combinatorial insights. We will expose in this paper a similar strategy for obtaining polynomial-time approximation algorithms. Our method features the use of approximation-preserving reductions, akin to the notion of parameterized reductions. We exemplify this method to obtain the currently best approximation algorithms for Harmless Set , Differential and Multiple Nonblocker , all of them can be considered in the context of securing networks or information propagation. [ABSTRACT FROM AUTHOR]