2014/10/30 by Marthe Bonamy, Bonamy, Marthe, Łukasz Kowalik +1
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1410.8336
openalex publication_date 2014/10/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We show a kernel of at most 13k vertices for the Planar 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.