A 43k Kernel for Planar Dominating Set using Computer-Aided Reduction Rule Discovery

Abstract

In this thesis we explore the technique of Region Decomposition for finding kernels for Planar Dominating Set. We redefine some concepts used in earlier work, fixing some ambiguities on the way. From those concepts we end up at the 335k kernel upper bound from Alber et. We then build on the results of Chen et al. to improve this upper bound to 55k. In the last part of the thesis we make use of a computer program to exhaustively search for reduced instances of regions, to be used together with the Region Decomposition technique. From the results from the computer program we are able to conclude that any region used in a Region Decomposition always can be reduced to an equivalent region having 12 vertices or less, in addition to its to endpoints. This let us arrive at a 43k kernel for Planar Dominating Set.