Polynomial-time data reduction for DOMINATING SET
Dealing with the NP-complete DOMINATING SET problem on, graphs, we demonstrate the power of data reduction by preprocessing from a theoretical as well as a practical side. In particular, we prove that DOMINATING SET restricted to planar graphs has a so-called problem kernel of linear size, achieved by two simple and easy-to-implement reduction rules. Moreover, having implemented our reduction rules, first experiments indicate the impressive practical potential of these rules. Thus, this work seems to open up a new and prospective way how to cope with one of the most important problems in graph theory and combinatorial optimization.
data reduction dominating set problem kernel theory algorithms np-complete problems plannar graphs fixed-parameter tractability