Polynomial Time Data Reduction for Dominating Set

Jochen Alber, Michael R. Fellows, Rolf Niedermeier

Dealing with the NP-complete Dominating Set problem on undirected graphs, we demonstrate the power of data reduction by preprocessing from a theoretical as well as a practical side…