Inhalt
zur Navigation
Es gibt keine deutsche Übersetzung dieser Webseite.
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 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. |