A 13k-kernel for planar feedback vertex set via region decomposition

作者：Bonamy Marthe^*; Kowalik Lukasz

来源：Theoretical Computer Science, 2016, 645: 25-40.

DOI：10.1016/j.tcs.2016.05.031

• Fixed parameter tractability
• Feedback vertex set
• Kernels
• Planar graphs

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.

• 出版日期2016-9-13