zbMATH — the first resource for mathematics

A polynomial kernel for Proper Interval Vertex Deletion. (English) Zbl 1366.68092
Epstein, Leah (ed.) et al., Algorithms – ESA 2012. 20th annual European symposium, Ljubljana, Slovenia, September 10–12, 2012. Proceeding. Berlin: Springer (ISBN 978-3-642-33089-6/pbk). Lecture Notes in Computer Science 7501, 467-478 (2012).
Summary: 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 affirmative by obtaining a polynomial kernel for Proper Interval Vertex Deletion. This resolves an open question of R. van Bevern et al. [Lect. Notes Comput. Sci. 6410, 232–243 (2010; Zbl 1309.68158)].
For the entire collection see [Zbl 1246.68031].

68Q25 Analysis of algorithms and problem complexity
05C62 Graph representations (geometric and intersection representations, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
Full Text: DOI