TU Berlin

Talk 27.04.2011


Page Content

to Navigation

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

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.


27.04.2011 16:15
René van Bevern
FR 6510

* Language is depending on the audience.

Back to overview.

J. Alber, M. R. Fellows, and R. Niedermeier. Polynomial-time data reduction for dominating set. J. ACM, 51(3):363-384, 2004.
H. L. Bodlaender. Kernelization: New upper and lower bound techniques. In Proc. 4th IWPEC, volume 5917 of LNCS, pages 17-37. Springer, 2009.
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.
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.
S. Thomassé. A 4k^2 kernel for feedback vertex set. ACM Trans. Algorithms, 6(3): 32:1-32:8, 2010.


Quick Access

Schnellnavigation zur Seite über Nummerneingabe