A 14$k$-Kernel for Planar Feedback Vertex Set via Region Decomposition
Abstract
We show a kernel of at most 14k vertices for the Planar Feedback Vertex Set problem. This improves over the previous kernel of size bounded by 97k. Our algorithm has a few new reduction rules. However, our main contribution is an application of the region decomposition technique in the analysis of the kernel size.
Origin | Files produced by the author(s) |
---|
Loading...