Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4952512 | Theoretical Computer Science | 2016 | 16 Pages |
Abstract
We show a kernel of at most 13k vertices for the Feedback Vertex Set problem restricted to planar graphs, i.e., a polynomial-time algorithm that transforms an input instance (G,k) to an equivalent instance with at most 13k vertices. To this end we introduce a few new reduction rules. However, our main contribution is an application of the region decomposition technique in the analysis of the kernel size. We show that our analysis is tight, up to a constant additive term.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Marthe Bonamy, Åukasz Kowalik,