Sie sind hier

## 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:

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.

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.