Parametric duality and kernelization: Lower bounds and upper bounds on kernel size Conference Paper

abstract

• We develop new techniques to derive lower bounds on the kernel size for certain parameterized problems. For example, we show that unless P = NP, PLANAR VERTEX COVER does not have a problem kernel of size smaller than 4k/3, and PLANAR INDEPENDENT SET and PLANAR DOMINATING SET do not have kernels of size smaller than 2k. We derive an upper bound of 67k on the problem kernel for PLANAR DOMINATING SET improving the previous 335k upper bound by Alber et al. Springer-Verlag Berlin Heidelberg 2005.

name of conference

• STACS 2005, 22nd Annual Symposium on Theoretical Aspects of Computer Science, Stuttgart, Germany, February 24-26, 2005, Proceedings

authors

• Chen, Jianer

published proceedings

• Lecture Notes in Computer Science

author list (cited authors)

• Chen, J., Fernau, H., Kanj, I. A., & Xia, G.

complete list of authors

• Chen, J||Fernau, H||Kanj, IA||Xia, G

publication date

• September 2005

publisher

• SIAM Journal on Computing  Publisher

published in

• Lecture Notes in Artificial Intelligence  Journal

URI

• https://hdl.handle.net/1969.1/182186

start page

• 269

end page

• 280

volume

• 3404