A 14k-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 metadatas

Contributor : Alexandre Pinlou <>
Submitted on : Friday, January 29, 2016 - 11:57:04 AM
Last modification on : Tuesday, December 10, 2019 - 4:08:05 PM

Links full text




Marthe Bonamy, Lukasz Kowalik. A 14k-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