A POLYNOMIAL KERNEL FOR PROPER INTERVAL VERTEX DELETION

被引：30

作者：

Fomin, Fedor V. ^{[1
]}

Saurabh, Saket ^{[2
,3
]}

Villanger, Yngve ^{[1
]}

机构：

[1] Univ Bergen, Dept Informat, N-5008 Bergen, Norway

[2] Inst Math Sci, Madras 600113, Tamil Nadu, India

[3] Univ Bergen, N-5008 Bergen, Norway

来源：

SIAM JOURNAL ON DISCRETE MATHEMATICS | 2013年 / 27卷 / 04期

基金：

欧洲研究理事会;

关键词：

kernelization; parameterized complexity; proper interval graph; vertex deletion; sunflower lemma;

D O I：

10.1137/12089051X

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

It is known that the problem of deleting at most k vertices to obtain a proper interval graph (Proper Interval Vertex Deletion) is fixed parameter tractable. However, whether the problem admits a polynomial kernel or not was open. Here, we answer this question in the affirmative by obtaining a polynomial kernel for Proper Interval Vertex Deletion. This resolves an open question of van Bevern et al. [Graph-Theoretic Concepts in Computer Science (WG 2010), Lecture Notes in Comput. Sci. 6410, Springer, Berlin, 2010, pp. 232-243].

引用

页码：1964 / 1976

页数：13

共 22 条

[1] Brandstdt A., 1999, Graph Classes: A Survey. SIAM Monographs on Discrete Mathematics and Applications
[2] Fixed-parameter tractability of graph modification problems for hereditary properties
Cai, LZ
[J]. INFORMATION PROCESSING LETTERS, 1996, 58 (04) : 171 - 176
[3] Cao Y., 2012, PREPRINT
[4] Parameterized enumeration, transversals, and imperfect phylogeny reconstruction
Damaschke, P
[J]. THEORETICAL COMPUTER SCIENCE, 2006, 351 (03) : 337 - 350
[5] Downey R. G., 1999, MG COMP SCI
[6] Erdos Paul, 1960, J. London Math. Soc., V35, P85
[7] Flum J., 2006, TEXTS THEORET COMPUT
[8] INCIDENCE MATRICES AND INTERVAL GRAPHS
FULKERSON, DR
GROSS, OA
[J]. PACIFIC JOURNAL OF MATHEMATICS, 1965, 15 (03) : 835 - +
[9] CHARACTERIZATION OF COMPARABILITY GRAPHS + OF INTERVAL GRAPHS
GILMORE, PC
HOFFMAN, AJ
[J]. CANADIAN JOURNAL OF MATHEMATICS, 1964, 16 (03): : 539 - &
[10] Golumbic MC., 1980, Algorithmic Graph Theory and Perfect Graphs

← 1 2 3 →