Data reductions and combinatorial bounds for improved approximation algorithms

• We introduce data reduction rules for obtaining approximation algorithms for maximization problems.
• These rules are combined with certain combinatorial insights often typical for kernelization algorithms.
• The resulting algorithms are of a combinatorial nature, yet better than previous published work in at least two special cases.
• We discuss several concrete problems that are natural maximization versions of well-studied domination-type graph problems.

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.