René van Bevern (TU Berlin)

Over the last years, reduction to a problem kernel, or kernelization for short, has developed into a very active research area within parameterized complexity analysis and the algorithmics of NP-hard problems in general [2]. In a nutshell, a kernelization algorithm transforms in polynomial time an instance of a (typically NP-hard) problem to an equivalent instance whose size is bounded by a function of a parameter. Nowadays, it has become a standard challenge to minimize the size of problem kernels. Consider the following examples:

1. For Feedback Vertex Set (given an undirected graph G and a positive integer k, find at most k vertices whose deletion destroys all cycles in G), there first has been an O(k^{11})-vertex problem kernel [3], improved to an O(k^3)- vertex problem kernel and finally to an O(k^2)-vertex problem kernel [5]
2. For Dominating Set on planar graphs (given an undirected planar graph G and a positive integer k, find at most k vertices such that each other vertex in G has at least one neighbor in the set of selected vertices), there first was a 335k-vertex problem kernel [1], which was further refined into a 67k-vertex problem kernel [4], both computable in O(n^3) time.

From the viewpoint of practical relevance, however, also the running times of kernelization algorithms have to be optimized. We show an O(k)-size problem kernel for Dominating Set in planar graphs that is computable in O(n) time.

* Language is depending on the audience.

Back to overview.