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

被引：0

作者：

Chen, JN ^{[1
]}

Fernau, H

Kanj, IA

Xia, G

机构：

[1] Texas A&M Univ, Dept Comp Sci, College Stn, TX 77843 USA

[2] Univ Newcastle, Sch Elect Engn & Comp Sci, Newcastle, NSW 2308, Australia

[3] Univ Tubingen, Wilhelm Schickard Inst Informat, D-72076 Tubingen, Germany

[4] Depaul Univ, Sch Comp Sci Telecomm & Informat Sci, Chicago, IL 60604 USA

来源：

STACS 2005, PROCEEDINGS | 2005年 / 3404卷

关键词：

kernelization; parameterized complexity;

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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.

引用

页码：269 / 280

页数：12

共 15 条

[1] Polynomial-time data reduction for DOMINATING SET
Alber, J
Fellows, MR
Niedermeier, R
[J]. JOURNAL OF THE ACM, 2004, 51 (03) : 363 - 384
[2] Parameterized complexity: exponential speed-up for planar graph problems
Alber, J
Fernau, H
Niedermeier, R
[J]. JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 2004, 52 (01): : 26 - 56
[3] Graph separators: a parameterized view
Alber, J
Fernau, H
Niedermeier, R
[J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2003, 67 (04) : 808 - 832
[4] Bar-Yehuda R., 1985, ANN DISCRETE MATH, V25, P27, DOI DOI 10.1016/S0304-0208(08)73101-3
[5] Vertex Cover: Further observations and further improvements
Chen, J
Kanj, IA
Jia, WJ
[J]. JOURNAL OF ALGORITHMS, 2001, 41 (02) : 280 - 301
[6] Dinur I, 2002, ANN IEEE SYMP FOUND, P33, DOI 10.1109/SFCS.2002.1181880
[7] DOWNEY R, 1999, PARAMETERIZED COMPLE
[8] Downey Rodney G., 1999, Contemporary Trends in Discrete Mathematics: From DIMACS and DIMATIA to the Future, V49, P49
[9] FELLOWS M, 2002, ELECT NOTES THEORETI, V61
[10] Fellows MR, 2000, LECT NOTES COMPUT SC, V1974, P240

← 1 2 →