Skip to Main content Skip to Navigation
Conference papers

A 14$k$-Kernel for Planar Feedback Vertex Set via Region Decomposition

Marthe Bonamy 1 Lukasz Kowalik 2 
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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.
Complete list of metadata

Cited literature [23 references]  Display  Hide  Download
Contributor : Alexandre Pinlou Connect in order to contact the contributor
Submitted on : Tuesday, February 4, 2020 - 3:54:22 PM
Last modification on : Friday, August 5, 2022 - 3:02:53 PM
Long-term archiving on: : Tuesday, May 5, 2020 - 5:54:56 PM


Files produced by the author(s)




Marthe Bonamy, Lukasz Kowalik. A 14$k$-Kernel for Planar Feedback Vertex Set via Region Decomposition. IPEC: International Symposium on Parameterized and Exact Computation, Sep 2014, Wroclaw, Poland. pp.97-109, ⟨10.1007/978-3-319-13524-3_9⟩. ⟨lirmm-01264417⟩



Record views


Files downloads