### Page Content

## Linear-Time Computation of a Linear Problem Kernel for Dominating Set on Planar Graphs

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:

- 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] - 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 335*k*-vertex problem kernel [1], which was further refined into a 67*k*-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.

date | speaker | location | language |
---|---|---|---|

27.04.2011 16:15 | René van Bevern | FR 6510 | german/ english* |

* Language is depending on the audience.

[1] | J. Alber, M. R. Fellows, and R. Niedermeier. Polynomial-time data reduction for dominating set. J. ACM, 51(3):363-384, 2004. |

[2] | H. L. Bodlaender. Kernelization: New upper and lower bound techniques. In Proc. 4th IWPEC, volume 5917 of LNCS, pages 17-37. Springer, 2009. |

[3] | K. Burrage, V. Estivill-Castro, M. R. Fellows, M. A. Langston, S. Mac, and F. A. Rosamond. The undirected feedback vertex set problem has a poly(k) kernel. In Proc. 2nd IWPEC, volume 4169 of LNCS, pages 192-202. Springer, 2006. |

[4] | J. Chen, H. Fernau, I. A. Kanj, and G. Xia. Parametric duality and kernelization: Lower bounds and upper bounds on kernel size. SIAM J. Comput., 37(4):1077-1106, 2007. |

[5] | S. Thomassé. A 4k^2 kernel for feedback vertex set. ACM Trans. Algorithms, 6(3): 32:1-32:8, 2010. |