A polynomial kernel for proper interval vertex deletion
SIAM Journal on Discrete Mathematics, 2013•SIAM
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.
(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.
It is known that the problem of deleting at most 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].
Society for Industrial and Applied Mathematics