A POLYNOMIAL KERNEL FOR PROPER INTERVAL VERTEX DELETION

作者：Fomin Fedor V^*; Saurabh Saket; Villanger Yngve

来源：SIAM Journal on Discrete Mathematics, 2013, 27(4): 1964-1976.

DOI：10.1137/12089051X

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

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].

• 出版日期2013